Search code examples
time-complexitybig-ocomplexity-theory

Finding Big O of the Harmonic Series

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

Solution

  • This follows easily from a simple fact in Calculus:

    enter image description here

    and we have the following inequality:

    enter image description here

    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.