A First Taste of Algorithms · The Algorithm That Flips Coins

The trick under the notebook

One debt from Chapter 4 remains unpaid. The notebook — Python’s dictionary — answers “is this question already written down?” essentially instantly, on notebooks of any size. Lists can’t do that (finding a thing in an unsorted list is Chapter 1’s linear search). What is the dictionary doing?

It is gambling, and winning the same way quicksort does. The scheme is called hashing: keep k buckets; put each key through a fixed scrambling function — the hash function — that turns the key into a bucket number, spreading keys across buckets like a fair die; to look a key up, recompute its bucket number and look only there. One arithmetic step to find the bucket, and then a search within it — fast exactly when buckets stay small.

So everything turns on collisions: different keys landing in the same bucket. How soon do collisions appear? That question has a famous, disguised twin. A class of k students, 365 possible birthdays: how likely is it that some two students share one? Intuition says you’d need a hundred-plus students for an even chance. The truth — compute it, then simulate it in the lab until belief arrives — is 23. With 23 people, the probability of a shared birthday already exceeds one half (0.507, exactly); at 50 people it is 0.97. The reason intuition fails by a factor of five: you instinctively count people, but collisions are about pairs, and 23 people contain 253 pairs — each pair an unlikely coincidence, but 253 lottery tickets add up. (The Diamond has you prove the threshold of 23 with one inequality from Book 2 and no calculator, via a numerical coincidence so clean it feels illegal.)

Figure 7.2 — The birthday curve: probability of a shared birthday against group size, crossing one-half at 23 and saturating by 50.

The birthday arithmetic delivers hashing’s honest verdict, both halves. The pessimistic half: collisions arrive shockingly early — around √k keys into k buckets — so no hash table outruns collisions, and the design must survive them (each bucket holds a little list; lookups search it). The optimistic half: early collisions are not many collisions. Keep roughly as many buckets as keys, and the average bucket holds about one item — so the average lookup is an arithmetic step plus a glance: constant time, on average, by the same logic that priced the hats. Chapter 4’s miracle, retroactively explained: the notebook was fast because it was gambling on a fair scramble, and the gamble concentrates just like quicksort’s. The two halves of this chapter are one idea wearing two costumes — randomness, honestly priced, converts worst-case dread into average-case contracts you can measure, trust, and build on.

Deeper water: the average, exactly

Quicksort’s expected comparisons, by linearity. Sort distinct items; name them by rank, 1 through n. Decompose: for each pair i < j, let the pair’s contribution be 1 if i and j are ever compared, else 0; the total comparisons is the sum over all pairs.

When are ranks i and j compared? Only when one of them is chosen as a pivot while both are still in the same sublist — and the sublist containing both always contains the whole stretch i, i+1, …, j (nothing between them can leave for the other side before they’re separated). Watch that stretch of j − i + 1 items: the first of them to be picked as a pivot decides everything. If it’s i or j, they are compared (the pivot meets everyone present); if it’s anything strictly between, they are sent to opposite sides, never to meet. By the fairness of the coins, each of the j − i + 1 candidates is equally likely to be first, so

P(i, j compared) = 2 / (j − i + 1).

Adjacent ranks are always compared (2/2 = 1 — someone must separate them, and only they themselves can); the extreme pair almost never (2/n). Sum over all pairs, group by distance d = j − i, and the sum telescopes into harmonic numbers: E = 2(n+1)Hₙ − 4n, where Hₙ = 1 + ½ + ⅓ + … + 1/n ≈ ln n. Hence E ≈ 2n ln n for large n — with the honest small-print this book owes you: at n = 256 the exact formula gives ≈ 2,125 while the asymptotic slogan says 2,839, a third too high. Your histogram’s hill will sit on the exact number, not the slogan. Asymptotics are shadows; at toy sizes, measure.

Deeper water: two kinds of gambler

Quicksort’s gamble never risks the answer — every run sorts correctly; only the time is random. Algorithms of this temperament are called Las Vegas. The other temperament — fixed time, but a small probability of a wrong answer — is called Monte Carlo, after the vignette’s method, and it is not a compromise for the desperate: the fastest known ways to test whether a 600-digit number is prime are Monte Carlo, wrong with probability less than one in 2¹⁰⁰ per run — and runs can be repeated, squaring the doubt away, until the error probability is dwarfed by the chance of the computer being struck by a meteor mid-calculation. At that point, philosophy must decide what “knowing” ever meant; engineering, sensibly, ships it. (Your phone performed such a test, several times, the last time it opened a secure connection.)

Where this leaves us

Predictability was the vulnerability: any fixed rule, read by an adversary, has a killer input. Coins removed the vulnerability by removing the readability — bad inputs became bad luck, and bad luck, priced by linearity and verified by histogram, turned out to be a tight hill far from the cliff. The same gamble runs the dictionary: scramble fairly, collide early but thinly, answer in constant time on average. And “average” itself was promoted from a vague comfort to a computed, concentrated, instrument-checked quantity.

Hold that promotion carefully, because the book’s second act now begins, and it runs on nothing else. Chapter 8 asks what it means for a machine to learn — and the answer, it will turn out, is built from this chapter’s materials: a quantity averaged over examples, minimized by a greedy walk, trusted not because any single answer is guaranteed but because the average is honest and the distribution concentrates. “Approximately correct, on average” sounds like a retreat from Chapter 1’s two questions. It is actually their final form.

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