Two programs can both be right and be nothing alike. Race them, watch the gap, and meet the question that turns programming into computer science.
Two programs can both give the right answer and still be nothing alike — one finishes before you look up, the other is still going tomorrow.
Up to now every level has been about getting it right. This one is about the question that comes immediately after, and it is the question that makes computer science a subject rather than a set of tricks: of the many correct ways, which one is good?
You already know this instinctively. Looking for a name in a phone book, you do not start at A and read every entry. You open it in the middle. Both work. One of them you would actually do.
Below are two copies of the same sorted list of 32 numbers, and one number to find. The top lane checks every box from the left. The bottom lane jumps to the middle and throws half the list away, over and over.
Pick a number, press go, and count the boxes each one has to look at.
Halving only works because the list is sorted. On a jumbled list, throwing half away is nonsense — the number could be in the half you binned. This is the trade you will meet everywhere this semester: a faster method usually demands something in return. Here it demands order.
On 32 boxes, one-at-a-time can take 32 looks and halving takes at most 6 — and only one target in the whole list actually needs that sixth look. Mildly interesting. Now watch what happens as the list grows, because this is the whole reason people study algorithms:
| list size | one at a time | halving |
|---|---|---|
| 32 | 32 looks | 6 looks |
| 1,000 | 1,000 looks | 10 looks |
| 1,000,000 | 1,000,000 looks | 20 looks |
| 8,000,000,000 | 8 billion looks | 33 looks |
Read the last row again. Every living human being, and you find the one you want in thirty-three questions. Each time the list doubles, halving needs exactly one more look. That is not a faster version of the same thing — it is a different kind of thing.
Later you will meet a notation for this — O(n) for one-at-a-time, O(log n) for halving. It looks like maths and it is really just a way of writing down the shape of that table: what happens to the work when the problem gets bigger? That is the only question the notation answers.
Person A thinks of a number from 1 to 100. Person B guesses 1, then 2, then 3… Count the guesses. Get bored. That boredom is the point.
Same game, but B always guesses the middle of what is left, and A answers only “higher” or “lower”. Count again. It will be seven or fewer, every time.
Then push it: 1 to 1,000 takes ten guesses. 1 to a million takes twenty. Try it and feel how little the game changes when the problem gets a thousand times bigger. Then ask the question that ruins it: what if A is allowed to lie once?
Six levels down. You can break a problem apart, write steps precise enough for something with no judgment, read the three shapes, trace values by hand, spot a problem you have already solved, and ask whether a correct answer is a good one.
The next six are the other half of what an intro course covers: what is actually inside the machine, why everything in it is numbers, what a variable really is, how conditions combine, how you know your work is right, and how order gets made.
Once it works, ask what it costs. Both answers can be correct and only one usable.
Halving needs a sorted list. Almost every speed-up demands something in return — find out what.
Not “how long does this take?” but “what happens when the input gets ten times bigger?”
Not recall — these are the shapes an exam actually uses. Every answer below was produced by compiling and running the code, so if you disagree with one, the compiler is the one to believe.
Have a real go before revealing. Being wrong here is worth more than being right in three weeks.
A sorted list of 1,000 items. Checking one at a time, how many might you have to look at in the worst case?
Same list of 1,000, but halving each time. How many looks now, at most?
What does halving require that checking-one-at-a-time does not?
← back to all 12 levels · stuck on anything? ask peter.