The Shape of the Curve
Last timeCounting Steps, Not Seconds
Almost all work falls into a handful of growth shapes. Knowing them in order, and knowing what each does when the input doubles, is most of the practical value of the subject.
The previous lesson produced expressions such as and
. This one throws away almost all of that detail and keeps
the part that decides things.
| 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 |
The ladder
The last column is the one to memorise, because it compresses the whole table
into six answers. The quadratic row is where usable stops: a million rows
compared pairwise is a million million operations, which is hours on a machine
that does a billion a second. The exponential row is not a performance problem
at all. At a hundred items its count already has thirty one digits, and no
machine that will ever be built finishes it, which is why the honest word for
exponential work is impossible rather than slow. Notice also how little
separates the top three rows at any size, and how little that separation
matters next to the gap below them.
What doubling does
The most useful sentence about each shape concerns what happens when the
input doubles. Constant stays put. Logarithmic gains one step. Linear
doubles. Linear times logarithmic a little more than doubles. Quadratic
quadruples. Cubic multiplies by eight. 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 lesson stops here
3 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents