question_id's blog

What is the complexity of this series?
By question_id, history, 10 years ago, In English

I could not understand the complexity of this series. N/1+N/2+N/3+N/4+.....+N/N.

cAN ANYONE EXPLAIN ME? tHANKS.

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

»
10 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

given series : N(1 + 1/2 + 1/3 + ... + 1/N) converges to N(log(N)). https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it +26 Vote: I do not like it

    There is no such notion as "Sequence A converges to sequence B", especially if they both diverge. What converges is their ratio and it converges to 1.

    → Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +7 Vote: I do not like it

Take n common, expression becomes : n * (1 + 1 / 2 + ... + 1/ n)

The expression (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by ln(n). Hence overall complexity is O(n * logn).

Proof: Let us integrate 1 / x from 1 to n. (Note that we are doing integration, which means sum of area under the curve 1/x, which is greater than (1 + 1 / 2 + ... + 1 / n). Integration of 1/x dx is ln(x).

→ Reply