CODEWITHSUNDEEP
algorithmdiscrete-mathematicsasymptotic-complexity
Michael Guantonio
Michael Guantonio

Reputation: 409

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.

Upvotes: 7

Views: 4852

Answers (3)

JB King
JB King

Reputation: 11910

The first example is O(N^2) and What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop? would be the question that answers that where the key is to note that the inner loop's number of rounds is dependent on n.

The second example is likely O(n log n) since the outer loop is being incremented on a different scale than linear. Look at binary search for an example of a logarithmic complexity case. In the second example, the outer loop is O(log n) and the inner loop is O(n) which combine to give a O(n log n) complexity.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

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.

Upvotes: 9

Michael Goldshteyn
Michael Goldshteyn

Reputation: 74360

Hopefully this isn't homework, but I do see that you at least made an attempt here, so here's my take on this:

cnt is incremented n*(n+1)/2 times, which makes the entire set of both loops O(n^2). The second loop is O(n/2) on the average, which is O(n).

Upvotes: 0

Related Questions