# What are harmonic numbers?

> The harmonic number H(n) = 1 + 1/2 + ... + 1/n grows like ln n. Why it appears in quicksort, hashing and the average analysis of algorithms.

**Harmonic numbers**: The n-th harmonic number is H(n) = 1 + 1/2 + 1/3 + ... + 1/n, which grows like the natural logarithm of n plus Euler's constant (about 0.5772).

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](https://cracked.guide/guide/knuth-w024-0), 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).

---

Source: https://cracked.guide/glossary/harmonic-numbers
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.