TAOCP Vol 1: Fundamental Algorithms · Week 24
TAOCP 1.2.7 Harmonic Numbers: reading guide
The harmonic numbers H_n = 1 + 1/2 + ... + 1/n, how they grow like ln n, and how to sum expressions involving them. They show up whenever you average over random positions.
Time About 4 hours this week
Why it matters
H_n is behind the average cost of quicksort, the expected number of times a running maximum changes, and the coupon collector problem. You will see it constantly in Vol 3.
Before you start
- 1.2.3 Sums and Products
- 1.2.2 Logarithms
How to approach it
Short section. Compute H_n for n up to 10 and compare to ln n + 0.577. Work through the summation by parts style manipulations 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
- Confusing H_n with ln n exactly; the difference tends to Euler's constant, it does not vanish.