Space Is a Cost As Well
Last timeBest Case, Worst Case, and the One You Get
Memory grows with the input too, it runs out more abruptly than time does, and it can be traded against time deliberately in both directions.
Everything so far has counted operations. A procedure also occupies memory,
that occupation grows with the input in exactly the same way, and it fails
differently when it runs out.
| time | extra memory | fails how | at a million items | |
|---|---|---|---|---|
| sum a list | 3 | 1 | 1 | 1 |
| sort a list in place | 4 | 1 | 1 | 1 |
| sort by building a new l | 4 | 3 | 2 | 2 |
| count co-occurring pairs | 5 | 5 | 2 | 3 |
Memory fails abruptly
Time degrades. A procedure that takes twice as long takes twice as long, and
somebody notices and complains.
Memory does not degrade. A procedure that needs slightly more memory than
exists does not run slightly worse; it slows by a factor of thousands as the
machine starts swapping, or it stops with an error. There is no gentle region
before the cliff, which is why memory is worth counting before the input gets
large rather than after.
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