Time complexity for the loop

Question

The outer loop executes n times while the inner loop executes ? So the total time is n*something.

Do i need to learn summation,if yes then any book to refer?

for(int i=1;i<=n;i++) 
  for(int j=1;j<=n;j+=i)
    printf("*");

How many times will the `printf()` run, given a particular value of `n`? That's the time complexity of this pair of nested loops. — O. Jones, Aug 20 '16 at 11:22
@OllieJones So you are saying for a given value k, the time complexity will be O(k).Lets say n=5, inner loop executes for 5 time for i=1, iterating i to 2,inner loop executes 3 times, now i=3 inner loop executes 2 times and i=4 inner loop executes 2 times. It varies with i. — srbh, Aug 20 '16 at 11:35
I think it prints floor(n/1) + floor(n/2) + ... + floor(n/n) times. — mm759, Aug 20 '16 at 11:42
The running time looks like a harmonic number to me. This [Math Stack Exchange article](http://math.stackexchange.com/questions/52572/do-harmonic-numbers-have-a-closed-form-expression) seems to say that there is no closed form. — Tim Biegeleisen, Aug 20 '16 at 12:06

score 4 · Answer 1 · edited May 23 '17 at 12:02

This question can be approached by inspection:

n = 16

i  |  j values         | # terms
1  |  1, 2, ..., 16    | n
2  |  1, 3, 5, ..., 16 | n / 2
.. |  ..               | n / 3
16 |  16               | n / n

In the above table, i is the outer loop value, and j values show the iterations of the inner loop. By inspection, we can see that the loops will take n * (1 + 1/2 + 1/3 + ... + 1/n) steps. This is a bounded harmonic series. As this Math Stack Exchange article shows, there is no closed form for the above expression in terms of n. However, as this SO article shows, there is an upper bound of O(n*ln(n)).

So, the running time for your two loops is O(n*ln(n)).

score 0 · Accepted Answer · edited Apr 13 '17 at 12:19

I believe the time complexity of that is O(n*log(n)). Here is why:

Let us pick some arbitrary natural number i and see how many steps the inner loop takes for this given i. Well for this i, you are going from j=1 to j<=n with a jump of i in between. So basically you are doing this summation many steps:

summation =  1 + (1+i) + (1+2i) + ... (1+ki)

where k is the largest integer such that 1+ki <= n. That is, k is the number of steps and this is what we want to solve for. Well we can solve for k in the equality resulting in k <= (n-1)/i and thus k = ⌊(n-1)/i⌋. That is, k is the floor function/integer division of (n-1)/i. Since we are dealing with time complexities, this floor function doesn't matter so we will just say k = n/i for simplicity. This is the number of steps that the inner loop will take for a given i. So we basically need to add all these for i = 1 to i <= n.

So numsteps will be this addition:

numsteps = n/1 + n/2 + n/3 + ... n/n
         = n(1 + 1/2 + 1/3 + ... 1+n)

So we need to find the sum of 1 + 1/2 + ... 1/n to finish this. There is actually no good closed form for this sum but it is on the order of ln(n). You can read more about this here. You can also guess this since the integral from 1 to n of 1/x is ln(n). Again, since we are dealing with time complexity, we can just use ln(n) to represent its complexity. Thus we have:

numsteps = n(ln(n))

And so the time complexity is O(n*log(n)).

Edit: My bad, i was calculating the sum :P

Time complexity for the loop

2 Answers2