Finding Big O of the Harmonic Series

Question

Prove that

1 + 1/2 + 1/3 + ... + 1/n is O(log n).  Assume n = 2^k 

I put the series into the summation, but I have no idea how to tackle this problem. Any help is appreciated

Answer 1

This follows easily from a simple fact in Calculus:

and we have the following inequality:

Here we can conclude that S = 1 + 1/2 + ... + 1/n is both Ω(log(n)) and O(log(n)), thus it is Ɵ(log(n)), the bound is actually tight.

Answer 2

Here's a formulation using Discrete Mathematics:

So, H(n) = O(log n)