Royboy01's blog

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

Sorry if its already been answered.

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

»
2 years 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
»
2 years 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
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good job bruh

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

Bibek..rocks

→ Reply
»
2 years 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