Is the time complexity of this code O(n^2) or O(nlogn)?

Question

for (int i = 1; i <= n; i++) {
   for (int j = 1; j <= n; j += i) {
       // some code
   }
}

The outer loop definitely runs n times. In case of the inner loop, assuming n = 8,

i	j
1	1, 2, 3, 4, 5, 6, 7, 8 ---> ran N times
2	1, 3, 5, 7 ---> ran N/2 times
3	1, 4, 7
4	1, 5
5	1, 6
6	1, 7
7	1, 8
8	1

I am confused whether the complexity should be logn or n for the inner loop. Any help will be greatly appreciated!

Answer 1

The outer loop iterates from i = 1 to n with a step size of 1. Therefore, the outer loop executes n times - linear time complexity.

The inner loop iterates from j = 1 to n with a step size of i. The step size i is dependent on the value of i in the outer loop.

As your table indicates;

• When i is 1, the inner loop executes n times.
• When i is 2, the inner loop executes n/2 times.
• When i is 3, the inner loop executes n/3 times.
• ...
• When i is n, the inner loop executes n/n times, which is 1.

The sum of these iterations becomes:

n + n/2 + n/3 + ... + 1

If we factor out n, we obtain the harmonic series:

1 + 1/2 + 1/3 + ... 1/n

whose time complexity is approximated to log(n). You can see a more detailed explanation here https://stackoverflow.com/a/25905474/12974735

So, in total your code has O(n log(n)) time complexity.