Big-O as an upper bound

Big-O is a ceiling. When we say an algorithm is O(n^2), we are promising that, once the input is large enough, its cost never rises faster than some constant multiple of n^2. It is like telling a friend 'the trip will take at most three hours' — a guarantee about the worst the growth can be, not a claim that it always hits that worst.

Formally, a function f(n) is O(g(n)) if there exist a positive constant c and a threshold n0 such that f(n) <= c times g(n) for every n >= n0. The two numbers c and n0 are called the witnesses: c absorbs the constant factor and n0 says 'I only promise this for large enough inputs'. For example, 3n^2 + 5n + 2 is O(n^2): pick c = 10 and n0 = 1, and indeed for all n >= 1 we have 3n^2 + 5n + 2 <= 3n^2 + 5n^2 + 2n^2 = 10n^2, because for n >= 1 each of n and 1 is at most n^2. Notice we replaced the smaller terms by n^2 to make the inequality easy — a typical proof trick.

A crucial honesty point: Big-O is an upper bound, so it can be loose. Every function that is O(n) is also O(n^2) and even O(2^n), the way 'at most three hours' is technically also 'at most a week'. So O(n^2) alone does not say the cost truly grows like n^2 — only that it grows no faster. To pin the growth down exactly you need Big-Theta. People often say 'O' loosely to mean 'is exactly', but strictly it only caps the growth from above.