7

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.

PengOne
  • 48,188
  • 17
  • 130
  • 149
Michael Guantonio
  • 409
  • 1
  • 6
  • 14
  • 1
    The first sample isn't in O(n), have you tried to print cnt after the loops using different values for n ? – Kwariz Sep 11 '12 at 18:35
  • @Kwariz I apologize. I meant that the first outer most loop in the first example is O(n). Not the entire collection of double for loops in the first example. – Michael Guantonio Sep 11 '12 at 18:37

3 Answers3

9

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • How do you combine the two loops in the second example though? Is it an added complexity so it is O(n) overall or is it multiplied together to give O(n log n) or is it something else? – JB King Sep 20 '12 at 14:44
  • @JBKing It is easier to compute the big-O for the second pair of loops together, because in this case we can use a [well-known formula for the sum of the first `N` elements of a geometric progression](http://en.wikipedia.org/wiki/Geometric_progression), which is `a*(1-r^(N+1))/(1-r)`. In our case, `a=1` and `r=2`, so the result is `(1-2^(n+1))/(1-2)`, or `2^(n+1)-1`. – Sergey Kalinichenko Sep 20 '12 at 14:58
0

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).

Michael Goldshteyn
  • 71,784
  • 24
  • 131
  • 181
  • For the second sample, the increment is not +2 but i is doubled ... shouldn't this smell like a complexity with logs ? – Kwariz Sep 11 '12 at 18:40
0

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.

Community
  • 1
  • 1
JB King
  • 11,860
  • 4
  • 38
  • 49