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

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

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.