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

Triplane

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.

Clubwoman

Thanks! My professor said we shouldn't use calculus for this one. Any tips on how to solve it using discrete math? – Triplane

For your purpose (i.e. proving the O(log(n)) upper bound), you only need to argue the leftmost inequality holds (i.e. 1/2 + 1/3 + ... + 1/(n+1) <= ln(n)), you can argue this by mathematical induction. (Hint: argue that we have 1/(n+1) <= log(n+1) - log(n) = log(1+1/n) using Taylor's expansion or otherwise) – Clubwoman

Answer 2

Here's a formulation using Discrete Mathematics:

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

Definitely

Answer 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, the number of times it runs = log(n) + 1 = O(log n).

Barony