How did the inner loop execute "n/i" times?

Question

I have a doubt regarding the time complexity of a code snippet and didn't quite understand the solution given.

function (n) {
           for(int i =0 ; i < n ; i ++){
                       for(int j = 0 ; j <= n ; j += i){
                                  printf("*");
                                      }

In the above code, it's given that inner loop executes n/i times for each value of i . And , overall time complexity is O(nlogn).

I can't figure out why the inner loop executes n/i times. Can someone please help me.

Answer 1

There are two loops, one incrementing i, and one incrementing j.

Given fixed i, for each pass of the j loop, j increments by i, until j reaches n.

So the values of j in each iteration are:

j
j + i
j + 2i
...
j + (n/i - j/i)i 

As you can see, this runs O(n/i) times.