55

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

3 Answers 3

78

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.

2
  • Thanks! My professor said we shouldn't use calculus for this one. Any tips on how to solve it using discrete math? Sep 18, 2014 at 6:29
  • 4
    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)
    – chiwangc
    Sep 18, 2014 at 9:17
19

Here's a formulation using Discrete Mathematics:

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

0

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.