big-O notation
/ big-OH /
When you describe how a car's fuel cost grows with distance, you do not list a value for every possible trip; you say 'it goes up roughly linearly with the miles'. Big-O notation does the same for running time: it throws away the unimportant detail (the exact constants, the small lower-order terms) and keeps the one thing that decides scalability, namely the dominant growth rate. It is the language we use to say 'this algorithm grows like n squared' without committing to a particular machine or a particular constant.
Precisely, we write f(n) = O(g(n)) to mean that, for large enough n, f(n) is at most some constant times g(n): there exist constants c > 0 and n0 such that f(n) <= c times g(n) for all n >= n0. So 3n^2 + 5n + 2 = O(n^2), because for big n the n^2 term swamps the rest and a constant like c = 4 absorbs the extras. Big-O is an upper bound. Its two companions complete the picture: big-Omega, written f(n) = Omega(g(n)), is a lower bound (f grows at least as fast as g), and big-Theta, f(n) = Theta(g(n)), means both at once (f grows exactly like g, up to constants). Together they are the grammar of growth rates.
Big-O is everywhere in this subject, and it carries two honest warnings. First, it is an upper bound on growth, not the exact running time: saying an algorithm is O(n^2) does not forbid it from also being O(n^3), and it does not promise it actually takes n^2 steps. To pin the growth down exactly you need big-Theta. Second, big-O hides constants and lower-order terms, which is fine for asking 'does it scale?' but dangerous if the hidden constant is enormous. A 10^100 times n algorithm is O(n) and useless. Use big-O to compare growth rates, not to predict the clock.
Take T(n) = 7n^2 + 100n + 4000. For small n the +4000 dominates, but as n grows the 7n^2 term wins, so T(n) = O(n^2) and also T(n) = Theta(n^2). It is true but weaker to say T(n) = O(n^3); it is false to say T(n) = O(n), because no constant times n can stay above 7n^2 for all large n.
Big-O keeps the dominant term and drops constants and lower-order terms.
Big-O is an UPPER bound, not an equality: O(n^2) also allows O(n^3) and does not claim the algorithm really takes n^2 steps; for an exact growth rate use big-Theta.