How work grows when the data grows
Four patterns of growth, with real numbers, and why the distance between them is enormous.
Once you start counting steps, something pleasant happens: nearly everything you will meet falls into one of a handful of patterns. This lesson walks through them with everyday examples and real numbers. There is no notation in this lesson at all. That comes later, once the patterns feel obvious.
The work does not grow
You have a stack of plates and you take the top one. That is one action. It is one action whether the stack holds five plates or five hundred, because you never touch the plates underneath.
Fetching the box at a known memory address behaves the same way, as does taking the item at a known index in a packed run. Ten items or ten million, the work is identical. Doubling the data changes nothing.
The work barely grows
This is the happiest pattern of the four. Some methods can throw away half of everything still in play at each step, so doubling the amount of data adds one extra step rather than doubling anything. Ten times the data does not cost ten times the work. It costs about three more steps. It is genuinely surprising the first time you meet it, so the next lesson is given over to it entirely.
The work grows in step with the data
Checking every name in a list to find one, as in the previous lesson. Ten names, up to ten checks. Twenty names, up to twenty. Double the data, double the work. This is the most common pattern of all, and it is not a bad one. It is simply proportional.
The work grows with the square
Here is the one to watch for. Everyone in a room shakes hands with everyone else, exactly once. How many handshakes?
With 4 people: the first person shakes 3 hands, the second has 2 left to shake, the third has 1, and the fourth has none remaining. That is 3 plus 2 plus 1, which is 6 handshakes. Now do it for larger rooms.
| People in the room | Handshakes | Compared to the row above |
|---|---|---|
| 4 | 6 | |
| 10 | 45 | 2.5 times the people, 7.5 times the handshakes |
| 100 | 4,950 | 10 times the people, 110 times the handshakes |
| 1,000 | 499,500 | 10 times the people, 101 times the handshakes |
Ten times as many people means roughly a hundred times as much work. The work is growing with the square of the number of people. Anything that compares every item with every other item behaves like this, and it is the reason such methods are fine on a hundred records and hopeless on a million.
The ratios in that last column come out slightly above the square at first: 7.5 rather than 6.25, then 110 rather than 100. That is worth explaining rather than glossing over. Each person shakes n minus 1 hands, not n, because nobody shakes their own, and in a small room that one missing handshake is a large fraction of the total. As the rooms get bigger the missing handshake stops mattering, which is why the last row has already settled to 101, and why larger rooms would sit closer and closer to a plain 100.
A fifth pattern, which has to wait
There is a fifth pattern, and it sits between growing in step with the data and growing with the square. The good methods for putting things into order land there, so it is not a curiosity. Counting it honestly needs one number you do not have yet, namely how many times a pile can be halved before it comes down to one, so it waits until the end of the next lesson, where that number is worked out rather than asserted.
The patterns side by side
This is the table to sit with. The numbers are approximate step counts, and the point is not the precise figures but the sheer distance between the columns. Do not try to take it in at a glance. Read one row at a time, left to right, and watch what the gap between the last two columns does as you go down.
| n | Does not grow | Barely grows | Grows in step | Grows with the square |
|---|---|---|---|---|
| 10 | 1 | about 3 | 10 | 100 |
| 100 | 1 | about 7 | 100 | 10,000 |
| 1,000 | 1 | about 10 | 1,000 | 1,000,000 |
| 1,000,000 | 1 | about 20 | 1,000,000 | 1,000,000,000,000 |
Look at the bottom row. If a single step took one billionth of a second, then a million steps takes about a thousandth of a second, which is instant. A million million steps at the same rate takes about a thousand seconds, which is roughly seventeen minutes. Same data, same machine, different pattern.
A method compares every pair of items in a collection. It handles 200 items in about one second. Roughly what happens if the collection grows to 2,000?
Ten times the items means roughly a hundred times the work, since the work grows with the square. So one second becomes about a hundred seconds, which is a little over a minute and a half. Growing to 20,000 items multiplies the work by roughly a hundred again: a hundred times a hundred seconds is 10,000 seconds, which is getting on for three hours.
The same patterns have a shape when you draw them. Below, each one is a line, named in the same words used above, showing how the steps pile up as the collection grows from 1 item to 100. The fifth pattern is drawn too, so you can see where it sits, even though its count is not worked out until the next lesson.