Big O Time Complexity for this code

Question

Given the following code -:

for(int i = 1; i <= N; i++)
    for(int j = 1; j <= N; j = j+i)
    {
        //Do something
    }

I know that the outer loop runs N times, and that the inner loop runs approximately log(N) times. This is because on each iteration of i, j runs ceil(N), ceil(N/2), ceil(N/4) times and so on. This is just a rough calculation through which one can guess that the time complexity will definitely be O(N log(N)).

How would I mathematically prove the same?

I know that for the ith iteration, j increments by ceil(N/2(i - 1)).

Answer 1

The total number of iterations of the inner loop for each value of i will be

i = 1: j = 1, 2, 3 ..., n ---> total iterations = n
i = 2: j = 1, 3, 5 ..., n ---> total iterations = n/2 if 2 divides n or one less otherwise
i = 3: j = 1, 4, 7 ..., n ---> total iterations = n/3 if 3 divides n or one less otherwise
...
i = m: j = 1, 1 + m, ... , n ---> total iterations ~ n/m
...
1

So approximately the total iterations will be (n + n/2 + n/3 ... + 1).

That sum is the Harmonic Series which has value approximately ln(n) + C so the total iterations is approximately n ln(n) and since all logarithms are related by a constant, the iterations will be O(nlogn).