### Dumbledore's blog

By Dumbledore, history, 6 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)? Comments (3)
 » 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)).
 » [Link](https://en.m.wikipedia.org/wiki/Harmonic_series_(mathematics)) divergence -> integral test
 » 6 years ago, # | ← Rev. 2 →   Already answered twice, but still: For the number of iterations (complexity) you have the sum : Where H n 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 H n - 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)