From charlesreid1

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.

We can make H_n as large as we please from observing that


H_{2^m} \geq 1 + \dfrac{m}{2}

This results from the fact that


H_{2^{m+1}} = H_{2^m} + \dfrac{1}{2^m+1} + \dfrac{1}{2^m + 2} + \dots + \dfrac{1}{2^{m+1}}

Now we have,


H_{2^m} + \dfrac{1}{2^m+1} + \dfrac{1}{2^m + 2} + \dots + \dfrac{1}{2^{m+1}} > H_{2^m} + \dfrac{1}{2^{m+1}} + \dfrac{1}{2^{m + 1}} + \dots + \dfrac{1}{2^{m+1}}

and the right side is


H_{2^m} + \frac{1}{2}

therefore


H_{2^m} \geq 1 + \dfrac{m}{2}

Flags