### Dumbledore's blog

By Dumbledore, history, 4 years ago, ,
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)?

• +17

 » 4 years ago, # |   +20 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)).
 » 4 years ago, # |   0 [Link](https://en.m.wikipedia.org/wiki/Harmonic_series_(mathematics)) divergence -> integral test
 » 4 years ago, # | ← Rev. 2 →   +6 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)