Calculus-Free Asymptotic for Harmonic Numbers

Here we prove that H_n = \Theta(\log_2 n) without touching calculus (the most common proof interprets H_n as a Riemann sum of \int 1/x ). Seeing as this is probably the most fundamental asymptotic for computer scientists, I was surprised to see this Stack Exchange question didn’t mention the calculus-free approach. The proof here pretty much matches my own answer to the Stack Exchange post.

We first consider powers of 2, n = 2^k. For these n, we can break up \sum \frac{1}{j} into the “chunks”

1

\frac{1}{2} + \frac{1}{3}

\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7}

\dots

\frac{1}{2^{k-1}} + \cdots + \frac{1}{2^k - 1}

and we have one extra term 1/2^k. There are k + 1 = \log_2 n + 1 chunks, and of course H_n is the sum of these chunks (plus the extra term), hence to show H_n = \Theta(\log_2 n) we show each chunk is \Theta(1). Inside each chunk we bound above by the power of 2:

1 \leq 1

\frac{1}{2} + \frac{1}{3} \leq \frac{1}{2} + \frac{1}{2} = 1

\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} \leq \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4}  =1

\dots

\frac{1}{2^{k-1}} + \cdots + \frac{1}{2^k - 1} \leq \frac{1}{2^{k-1}} + \cdots + \frac{1}{2^{k - 1}} = 1

Thus each chunk is at most 1, and taken together with the extra term \frac{1}{2^k}, we have H_n \leq \log_2 n + \frac{1}{2^k} \leq \log_2 n + 1.

On the other hand, if we lower bound the elements by the next power of 2,

1 \geq 1

\frac{1}{2} + \frac{1}{3} \geq \frac{1}{4} + \frac{1}{4} = \frac{1}{2}

\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} \geq \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}  =\frac{1}{2}

\dots

\frac{1}{2^{k-1}} + \cdots + \frac{1}{2^k - 1} \geq \frac{1}{2^k} + \cdots + \frac{1}{2^k} = \frac{1}{2}

Every chunk is at least \frac{1}{2}, hence H_n \geq \frac{1}{2}\log_2 n.

This essentially is the proof. One technicality: we’ve only shown H_n = \Theta (\log_2 n) for n a power of 2. Monotonicity of H_n completes the proof for all n: taking the nearest powers of 2 above and below n, call them n_- and n_+,

n/2 < n_- < n < n_+ < 2n

Applying our bounds on H_{n_-} and H_{n_+},

H_n \leq H_{n_+} \leq \log_2 n_+ + 1 < \log_2 (2n) +1= \log_2 n + 2

H_n \geq H_{n_-} \geq \frac{1}{2}\log_2 n_- > \frac{1}{2}\log_2 (n/2) = \frac{1}{2}\log_2 n - \frac{1}{2}

Thus H_n = \Theta(\log_2 n).

(In general, for any monotonic linear or sublinear function, it suffices to show \Theta(\cdot) on only the powers of 2).