Recall that O(n^2) means that the program has no inputs that cost more than this.

A proposed upper bound can be much higher than the actual cost of the program, and still be correct.