Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Complexity of a double for loop

I am trying to figure out the complexity of a for loop using Big O notation. I have done this before in my other classes, but this one is more rigorous than the others because it is on the actual algorithm. The code is as follows:

for(cnt = 0, i=1; i<=n; i++) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

AND

for(cnt = 0, i=1; i<=n; i*=2) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

I have arrived that the first loop is of O(n) complexity because it is going through the list n times. As for the second loop I am a little lost. I believe that it is going through the loop i times for each n that is tested. I have (incorrectly) assumed that this means that the loop is O(n*i) for each time it is evaluated. Is there anything that I'm missing in my assumption. I know that cnt++ is constant time.

Thank you for the help in the analysis. Each loop is in its own space, they are not together.

like image 223
Michael Guantonio Avatar asked Sep 11 '12 18:09

Michael Guantonio


1 Answers

The outer loop of the first example executes n times. For each iteration of the outer loop, the inner loop gets executed i times, so the overall complexity can be calculated as follows: one for the first iteration plus two for the second iteration plus three for the third iteration and so on, plus n for the n-th iteration.

1+2+3+4+5+...+n = (n*(n-1))/2 --> O(n^2)

The second example is trickier: since i doubles every iteration, the outer loop executes only Log2(n) times. Assuming that n is a power of 2, the total for the inner loop is

1+2+4+8+16+...+n

which is 2^Log2(n)-1 = n-1 for the complexity O(n).

For ns that are not powers of two the exact number of iterations is (2^(Log2(n)+1))-1, which is still O(n):

1      -> 1
2..3   -> 3
4..7   -> 7
8..15  -> 15
16..31 -> 31
32..63 -> 63

and so on.

like image 80
Sergey Kalinichenko Avatar answered Sep 30 '22 09:09

Sergey Kalinichenko