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.
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 n
s 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With