Week 26: TAOCP 1.2.10 Analysis of an Algorithm

A complete worked analysis of a simple algorithm (finding the maximum of n elements): best case, worst case, average, and full probability distribution of how often the running maximum changes. It is the template for every analysis in the series.

Time About 7 hours this week

Why it matters

This is the method behind every "average case O(n log n)" claim. Seeing it done end to end on a small example teaches you what those claims actually mean.

Before you start

1.2.7 Harmonic Numbers
1.2.9 Generating Functions
Basic probability: mean and variance

How to approach it

Write the algorithm in a real language, instrument it to count how often the max changes, and run it over many random permutations. Compare your measured mean to Knuth's formula. Then go through the probability generating function derivation with pencil.

Exercises

Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.

Traps

Skipping the variance. The mean alone hides how spread out the cost is.
Confusing the number of comparisons with the number of updates. Knuth counts specific steps.