Determining the time complexity of a double loop

Question

I'm trying to understand why the time complexity of the following loop:

for (int i = 1; i <= MAXN; i++)
     for (int j = i; j <= MAXN; j += i);

is $O(N\log N)$. From what I understand the inner loop should generate the harmonic series multiplied by a polynomial.

$$N+\frac{N}{2}+\frac{N}{3}+\cdots+ \frac{N}{N}= N\cdot\left(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{N}\right)\in N\cdot O(\log N) = O(N\log N)$$

I know that the Harmonic series grows logarithmically for large $N$, but I'm having trouble understanding how it was generated in the first place. It is not obvious from the above code.

Answer 1

It's all in that last increment j += i

First time through, j runs over all indices from 1 to MAXN. Second time through, j skips every other index. Third time through, j hits every third index. Fourth time through, every fourth index. etc.