'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

time-complexitybig-ocomplexity-theory


Solution 1:[1]

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.

Solution 2:[2]

Here's a formulation using Discrete Mathematics:

enter image description here So, H(n) = O(log n)

Solution 3:[3]

If the problem was changed to :

1 + 1/2 + 1/4 + ... + 1/n

series can now be written as:

1/2^0 + 1/2^1 + 1/2^2 + ... + 1/2^(k)

How many times loop will run? 0 to k = k + 1 times.From both series we can see 2^k = n. Hence k = log (n). So, number of times it ran = log(n) + 1 = O(log n).

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 chiwangc
Solution 2 Sushovan Mandal
Solution 3 Sahim Salem

Related Questions