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.
