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

neurite
  • 2,798
  • 20
  • 32
user2092408
  • 553
  • 1
  • 5
  • 4

3 Answers3

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.

chiwangc
  • 3,566
  • 16
  • 26
  • 32
  • Thanks! My professor said we shouldn't use calculus for this one. Any tips on how to solve it using discrete math? – user2092408 Sep 18 '14 at 06: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 '14 at 09:17
19

Here's a formulation using Discrete Mathematics:

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

Sushovan Mandal
  • 1,027
  • 3
  • 13
  • 32
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).

Sahim Salem
  • 59
  • 5