Dumbledore's blog

Dumb question on time complexity
By Dumbledore, history, 11 years ago, In English 
for (int i = 1; i <= MAXN; i++)
     for (int j = i; j <= MAXN; j += i);


Can anybody explain to me why the time complexity for this code is O(N log N)?

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

»
11 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

The time complexity is O(N + N/2 + N/3 + N/4 + ... + N/N) = O(N*(1 + 1/2 + 1/3 + ... + 1/N)).

But 1 + 1/2 + 1/3 + ... 1/N < log(N). (link)

=> O(N + N/2 + N/3 + N/4 + ... + N/N) = O(N*(1 + 1/2 + 1/3 + ... + 1/N)) = O(N*log(N)).

→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

[Link](https://en.m.wikipedia.org/wiki/Harmonic_series_(mathematics)) divergence -> integral test

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

Already answered twice, but still:

For the number of iterations (complexity) you have the sum :

Where Hn is the sum of the first n terms of the Harmonic series. Generally the harmonic series differs by a constant factor from the natural logarithm, more precisely, if n tends towards infinity then the difference Hn - ln(n) tends towards the Euler-Mascheroni constant which has a value of about 0.577, hence we get that the complexity is O(NlnN) = O(NlogN)

→ Reply