Time complexity of nested for loop inside while loop

Question

If there is a nested for loop inside while loop like this:

while(condition)
   for(i=0; i<size; i++)

the size in the for loop is increasing every time the for loop is being executed, starting at 1,2,...,n-1 and the while loop runs n-1 times.

That means that the time complexity is O(n^3)?

Answer 1

If by every time the for loop is being executed you mean every time the while(condition) triggers a new run of the for loop, then the time complexity is n².

That is, if you increment a counter inside the inner for loop, it will be incremented n * (n - 1) / 2 = n choose 2 times. But because constant factors and lower order terms are omitted in big O notation, we can just write n².

For illustration, consider this Python 2.7 implementation (I converted the outer while loop + size increment into a for loop):

n = 10
counter = 0

for size in range(1, n):
    for i in range(0, size):
        counter += 1
        print i,
    print
print

print "counter =", counter
print "n choose 2 =", n * (n - 1) / 2

Output:

0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 3 4 5
0 1 2 3 4 5 6
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 8

counter = 45
n choose 2 = 45

Try running it with different values of n to see that the formula holds true.