Reading the Cost Off the Work
Last timeWhy the Constants Get Dropped
Three patterns cover most of it: work done in sequence, work nested inside work, and work that halves what is left. Recognising them turns analysis into reading.
The previous lessons established the ladder and the convention. This one is
the working skill: looking at a piece of work and saying what shape it has.
Nearly all of it reduces to three patterns.
| repetitions | cost of the body | the total | typical example | |
|---|---|---|---|---|
| one pass over the input | 1 | 1 | 1 | 1 |
| a pass inside a pass | 2 | 1 | 2 | 2 |
| halving what is left | 3 | 1 | 3 | 3 |
| a pass, then a pass | 1 | 1 | 1 | 4 |
Sequence and nesting
Two loops one after the other add. By the previous lesson the sum keeps only
its larger part, so a linear pass bolted onto a quadratic procedure is free,
and speeding that pass up gains nothing at all.
Two loops one inside the other multiply, because the inner body runs once per
pass of the outer loop. That is the entire origin of quadratic cost.
| step | the work | outer repeats | inner work per pass | total |
|---|---|---|---|---|
| 1 | one loop over n items | n | constant | n |
| 2 | a loop over n, then another over n | n then n | constant | n, the sum reduced |
| 3 | a loop over n inside a loop over n | n | n | n squared |
| 4 | a loop over rows inside a loop over columns | r | c | r times c |
| 5 | a loop over n containing a list membership test | n | n, hidden | n squared |
| 6 | a loop over n containing a dictionary lookup | n | constant | n |
Halving
The third pattern is the one that has to be taught, because nothing in daily
experience prepares anyone for how few steps it takes.
The lesson stops here
1 more paragraph 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