A First Taste of Algorithms · Two Questions

Why “always” is the hard part

Look at the first demand again: the procedure must work for every possible input. This is a strange and strong demand, and it is what makes algorithms mathematics rather than folklore.

Suppose your friend claims a strategy for the guessing game and demonstrates it: she finds your number in six questions. Impressive — and it proves almost nothing. Maybe she was lucky. Maybe your number happened to sit somewhere her strategy reaches quickly. A demonstration is one input. A guarantee is all of them, and there are a hundred possible numbers — or a trillion, in the big version. You cannot check a trillion cases by playing a trillion games.

So how can anyone ever promise “always”? The same way mathematics always handles infinity and its little cousins: by an argument that covers every case at once without visiting any of them. For the halving strategy, the argument is short enough to say in one breath: after every question, the suspects that remain always form a single unbroken range that contains my number, and the range shrinks by at least half each time; a range under 1 cannot hide anything. Hold on to the first half of that sentence — “the survivors always form a range containing the answer.” A statement that stays true through every step of a procedure is the basic instrument for proving procedures correct, and it has a name we will meet in the deep water below.

The second demand — counting cost — needs its own honesty rule. When we count, we count the worst case: the most steps the procedure could possibly need, over all inputs. Not the lucky case, not the typical case (we’ll earn the right to talk about “typical” in Chapter 7, and it will take real probability to do it honestly). The worst case is the only promise you can make to someone who hasn’t told you their input yet. “At most seven questions” is a contract. “Usually around four” is a mood.

The obvious algorithm

Now put the game in the form computers actually meet ten billion times a day. You have a list of items — names, numbers, song titles — and a target, and the question is: is the target in the list, and where?

The obvious procedure: check the first item. Then the second. Keep going until you find the target or run out of list. This is linear search, and you should not look down on it. It is correct on every list — sorted, scrambled, repetitive, empty — and its correctness needs no cleverness to believe: if the target is anywhere, the march from front to back must step on it.

The cost: on a list of n items, up to n checks. There is the word from the honesty rule — up to. If the target sits in front, one check. If it sits at the back, n. And if the target is absent, exactly n, every time, with no luck possible: you cannot declare something missing until you have looked everywhere. Sit with that for a second, because it is the first genuinely useful insight of the book. Proving absence is expensive. Finding your keys takes until you find them; being sure they’re not in the house takes searching the whole house.

Unless — and this is the turn the whole chapter pivots on — the house is organized.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses