Royboy01's blog

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

Sorry if its already been answered.

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

»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Good job bruh

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Bibek..rocks

→ Reply
»
21 month(s) 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