math Common summations in computer science Sums of reciprocals: 1/1 + 1/2 + 1/3 + 1/4 + ...


Example

The summation

1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n

is equal to the nth harmonic number, denoted Hn. The nth harmonic number obeys the inequalities

ln (n + 1) ≤ Hn ≤ (ln n) + 1

and therefore Hn = Θ(log n). The harmonic numbers often arise in the analysis of algorithms, with randomized quicksort being a particularly nice example.