Asymptotic Notation

Two programmers argue about whose sort is faster. One times both on a 1000-element list; the other insists the answer depends on the machine, the language, the compiler, even the weather. They are both right — and both missing the point. What we actually want to compare is not a stopwatch reading but the shape of the growth: as the input n gets large, does the running time creep up like \log n, march up like n, or explode like 2^n?

Asymptotic notation is the language for that question. It throws away constant factors and low-order terms — the parts that depend on the machine — and keeps only the dominant growth rate, the part that is a property of the algorithm itself. You have met big-O informally; here we make the whole family — O, \Omega, \Theta, o, \omega — precise, and see exactly what each one claims.

Why growth rate is what matters

Suppose algorithm A runs in 100n steps and algorithm B in 2n^2. For a tiny input B wins — but there is a crossover, and past it A wins forever, by an ever-widening margin. Double the input and A's time doubles; B's quadruples. That is why we care about the eventual behaviour: for any input big enough to be worth worrying about, the faster-growing function loses, no matter how kind its constant.

The curves below are the growth rates you will meet again and again, drawn on one axis. Notice how brutally they separate: by n = 20 the exponential has left the polynomials far behind, and the logarithm is barely off the floor. This ranking — 1 \prec \log n \prec n \prec n\log n \prec n^2 \prec 2^n \prec n! — is the backbone of every complexity argument you will make.

The five relations, precisely

Each piece of notation compares a running-time function f(n) against a reference g(n) — think of g as a clean yardstick like n^2. All the definitions say the same kind of thing: "eventually, up to a constant factor, f is bounded like this."

f = O(g) — upper bound: there are constants c > 0 and n_0 with 0 \le f(n) \le c\,g(n) for all n \ge n_0. "f grows no faster than g."
f = \Omega(g) — lower bound: 0 \le c\,g(n) \le f(n) eventually. "f grows at least as fast as g."
f = \Theta(g) — tight bound: both at once, c_1 g(n) \le f(n) \le c_2 g(n). "f grows exactly like g." This is the one you usually want.
f = o(g) — strictly smaller: for every c > 0, eventually f(n) < c\,g(n); equivalently \lim_{n\to\infty} f(n)/g(n) = 0.
f = \omega(g) — strictly larger: the mirror image, \lim_{n\to\infty} f(n)/g(n) = \infty.

The clean mental model: O is like \le, \Omega like \ge, \Theta like =, and the little-o/little-\omega pair are the strict < and >. And f = \Theta(g) exactly when f = O(g) and f = \Omega(g).

The limit test — the quick way in practice

Chasing constants c, n_0 by hand is tedious. Usually the ratio f(n)/g(n) settles down, and its limit tells you everything:

\displaystyle \lim_{n\to\infty} \frac{f(n)}{g(n)}	Conclusion
0	f = o(g) (so also O(g), not \Theta(g))
a constant c > 0	f = \Theta(g)
\infty	f = \omega(g) (so also \Omega(g), not O(g))

For example, 3n^2 + 5n versus n^2: the ratio is 3 + 5/n \to 3, a positive constant, so 3n^2 + 5n = \Theta(n^2) — the 5n and the leading 3 both vanish from the classification. And \log n versus n: (\log n)/n \to 0, so \log n = o(n).

Written literally, n = O(n^2) and 2n = O(n^2) would let you conclude n = 2n — nonsense. The truth is that O(g) denotes a set of functions (all those bounded above by a multiple of g), and the "=" really means "\in": f \in O(g). The set notation is more honest, but the equals-sign convention is so entrenched — Knuth used it, everyone uses it — that you must simply read it one-directionally: O on the right is a claim about the left, never the reverse.

It is perfectly true that binary search is O(n^2) — that just says it grows no faster than n^2, which it certainly doesn't. But it is nearly useless: the tight bound is \Theta(\log n). Saying "the algorithm is O(n^2)" when you know it is \Theta(\log n) is not wrong, merely unhelpful — like saying a cheetah runs "at most 500 mph." When someone reports an algorithm's complexity, they almost always mean the tight \Theta bound; reserve a bare O for when you genuinely only have an upper bound (as with an unproven worst case). And beware the common slip of calling the best case an O — best/worst/average is a different axis from upper/lower bound entirely.

The rules you will use without thinking

Drop constants: \Theta(c \cdot f) = \Theta(f) for any constant c > 0.
Keep the biggest term: in a sum, the fastest-growing term wins — \Theta(n^2 + n\log n + n) = \Theta(n^2).
Products multiply: if f_1 = O(g_1) and f_2 = O(g_2) then f_1 f_2 = O(g_1 g_2) — this is how nested loops combine.
Logs beat polynomials beat exponentials: (\log n)^a = o(n^b) and n^b = o(2^{n}) for any fixed a, b > 0, no matter how big a or how small b.
Log bases don't matter: \log_2 n = \Theta(\log_{10} n) — changing base is just multiplying by a constant, so we write \log n inside asymptotics with no base at all.