Glossary
What are harmonic numbers?
The harmonic numbers are H(n) = 1 + 1/2 + 1/3 + ... + 1/n. They grow without bound but slowly, about ln n + 0.5772, and they appear whenever an algorithm's average behavior depends on the position of something random.
Where they show up
How many times does the running maximum change while scanning a random array? H(n) on average, minus one for the first element. How many comparisons does quicksort make on average? About 2(n + 1)H(n) minus a linear term, which is where its n log n comes from. The coupon collector problem, average search costs in random binary trees and the analysis of hashing all produce harmonic numbers.
Where it is taught
Knuth gives them their own section, §1.2.7, with the asymptotic formula and how to sum expressions involving H(n). The first place you use them is the "how many times does the maximum change" analysis in §1.2.10.
Questions
Is H(n) the same as log n?
Not exactly, but close: H(n) is ln n plus Euler's constant plus a correction that shrinks like 1/(2n).