AOCP/Harmonic Numbers

Volume 1

Chapter 1: Basic Concepts: Harmonic numbers

Harmonic numbers become important in analyses of algorithms. Define

$ H_n = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dots + \dfrac{1}{n} = \sum_{1 \leq k \leq n} \dfrac{1}{k} \qquad n \geq 0 $

While it does not occur often in classical mathematics, it crops up more often in algorithm analysis.