Royboy01's blog

How the time complexity of 1+1/2+1/3+....+1/n is O(log n)
By Royboy01, history, 19 months ago, In English

Sorry if its already been answered.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
19 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

We can approximate the sum of this infinite harmonic sequence with the natural log function (Think of it like integration instead of addition), and the error is less than $$$1$$$ (It's called the Euler-Mascheroni constant)

→ Reply
»
19 months ago, # |
  Vote: I like it +66 Vote: I do not like it

lets say it is smaller than 1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + ... (we have 1/2^i 2^i times) and (1/2^i) * 2^i = 1 so we have n * log(n)

→ Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Good job bruh

→ Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Bibek..rocks

→ Reply
»
19 months ago, # |
  Vote: I like it +4 Vote: I do not like it

We can apply integral test for it 1+/2+1/3+...+1/n < integral of (1/x)dx with lower limit 1 and upper limit n. So the sum is < log(n)

→ Reply