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)?
# | User | Rating |
---|---|---|
1 | ecnerwala | 3650 |
2 | Benq | 3582 |
3 | Geothermal | 3570 |
3 | orzdevinwang | 3570 |
5 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3532 |
8 | Radewoosh | 3522 |
9 | Um_nik | 3483 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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)?
Name |
---|
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
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)