A loop has an inner loop that depends on the outer variable. Is it still quadratic, and how can you see that from the operation count?
Yes, it is still quadratic, but the operation count shows you exactly how much of the quadratic you are really doing.
def count_pairs(n):
steps = 0
for i in range(n):
for j in range(i, n):
steps += 1
return steps
So here is the count. When the outer loop is on zero, the inner loop does n steps. When it is on one, it does n minus one. And when it is on n minus one, it does one. So the total is n plus n minus one plus n minus two and so on, all the way down to one, and that adds up to n times n plus one, all over two.
the outer loop is on the inner loop does
--------------------- ------------------
0 n
1 n - 1
2 n - 2
...
n - 1 1
the total is n(n + 1) / 2
So the answer is that it is O of n squared, and the constant is one half rather than one. That is a real saving and it is worth taking, but it does not change the shape, because doubling the input still makes the work four times as big.
So the rule to remember is this. Write down the number of steps for the first few rounds of the outer loop and look for the pattern, because the pattern tells you the bound and the constant in one go.
The next question in this topic looks at the same idea on a list of lists, and the last one at the harder case.