A First Taste of Algorithms

Chapter 7: The Algorithm That Flips Coins

✦ ✦ ✦

In which an adversary is defeated by dice, and an average earns the right to be trusted

The adversary

Here is a sorting algorithm with an old and excellent idea — quicksort. Pick one item from the list and call it the pivot. Walk the list once, dealing everything smaller than the pivot to its left and everything bigger to its right (one comparison per item: cost n − 1). The pivot now sits exactly where it belongs, forever. Sort the two sides — somehow, and by Chapter 3 you know what fills in “somehow.”

The bill depends entirely on the pivot’s quality, and you have already met both fates — they are Chapter 3’s two trees. A pivot near the middle splits the list in half: halving recursion, n work per level, log n levels, the n log n discount. A pivot at the extreme peels off one item and leaves n − 1: the lopsided vine you built in Lab 3’s Break-it 3, n levels, the n² bill, and (you watched this happen) a recursion n calls deep that the machine’s stack refuses.

Figure 7.3 — Two fates of a pivot: median pivots build Chapter 3’s balanced tree; extreme pivots grow Lab 3’s vine.

So everything rides on choosing pivots well — and here the trouble starts. Suppose the rule is simple and fixed: always take the first item. Now imagine an adversary: someone who knows your rule and supplies your input. Against first-item pivots, the adversary hands you an already-sorted list — the first item is the minimum, the worst pivot possible, at every level of the recursion. Your clever algorithm runs its full n² on the most innocent-looking input in the world, and in Lab 7 you will watch it die of exactly this. Change the rule — last item, middle item, some fixed recipe — and the adversary recomputes and ruins you again. This is the iron law of fixed strategies: any pivot rule the adversary can read, the adversary can defeat. The worst case isn’t an accident of one rule; it is a consequence of being predictable.

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