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 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
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)