Six growth shapes, and the one column worth memorising
Almost all work falls into a handful of shapes, and the useful question about each is what happens when the input doubles. That one sentence decides most design arguments before they start.
There is a version of this subject that is a semester of proofs, and a version that fits on a postcard and settles most real arguments. This is the postcard.
The ladder
| the shape | n = 100 | n = 10,000 | n = 1,000,000 | doubling n multiplies the cost by |
| constant | 1 | 1 | 1 | nothing: it is the same |
| logarithmic | 7 | 13 | 20 | nothing: it adds one step |
| linear | 100 | 10,000 | 1,000,000 | 2 |
| linear times logarithmic | 664 | 132,877 | 19,931,569 | a little over 2 |
| quadratic | 10,000 | 100,000,000 | 1,000,000,000,000 | 4 |
| exponential | a 31-digit number | a 3,011-digit number | a 301,031-digit number | it squares it |
Each rung is matched by work you already recognise: looking a key up in a hash table, halving a sorted list, scanning a list once, sorting it, comparing every pair, trying every subset.
The last column is the one to learn, because it compresses the whole table into six answers. Constant stays put. Logarithmic gains one step. Linear doubles. Linear times logarithmic a little more than doubles. Quadratic quadruples. Exponential squares.
That last one deserves its own line. Squaring is not a slowdown, it is a wall: a procedure taking a second at forty items takes about three hundred years at eighty. The honest word for exponential work is impossible rather than slow.
Where usable stops
The quadratic row is the boundary. A million rows compared pairwise is a million million operations, which is hours on a machine doing a billion a second.
Notice also how little separates the top three rows at any size, and how little that separation matters next to the gap below them. Arguments about whether something is linear or linear times logarithmic are usually not worth having. Arguments about whether it is linear or quadratic always are.
Reading the shape off timings, without reading the code
The doubling rule works backwards, which is how you establish the shape of code nobody wants to read, including library code and other people's services.
Measure at sizes that double, then look at the ratio between consecutive times rather than the times themselves.
| size | A, ms | B, ms | C, ms |
| 1,000 | 1.1 | 0.9 | 1.2 |
| 2,000 | 2.2 | 3.6 | 2.6 |
| 4,000 | 4.3 | 14.5 | 5.5 |
| 8,000 | 8.7 | 58.1 | 11.9 |
| ratio between rows | about 2 | about 4 | about 2.2 |
| the shape | linear | quadratic | linear times logarithmic |
Only the ratios are read, never the times, which is what makes the method independent of the machine it ran on. A ratio near one is constant or logarithmic, near two is linear, near four is quadratic, near eight is cubic, and a ratio that itself grows is something worse. The hard case is telling 2 from 2.2, and it is settled by going further out: at a hundred times the size, C drifts upward and A stays at two.
The curves cross, and below the crossing the worse shape wins
A better growth shape does not win at every size. Insertion sort compares every pair in the worst case and still beats merge sort below a few dozen items, because its per-item work is tiny and merge sort allocates and copies. Serious sorting libraries exploit exactly this: they sort small pieces with the quadratic method and switch above a threshold found by measurement.
And it is why quadratic code reaches production: on a developer's sample of fifty rows, the quadratic curve looks completely fine.
From the library
How Long It Takes
Eight lessons: counting steps rather than seconds, the shape of the curve, why the constants get dropped, best case against the one you actually get, space as a cost, occasionally expensive and usually free, and when the analysis lies.
It opens the track that ends with telling in advance which approach survives a million rows. The first lesson is free to read.