Big-O Notation

Bounding growth up to constants; polynomials vs exponentials.

The idea

Big-O notation compares functions by how fast they grow, ignoring constant factors and small inputs. It is the standard measure of an algorithm's cost: the exact step count depends on the machine, but the rate of growth does not.

For functions $f$ and $g$ of a positive integer $n$, we write

$f(n) = O(g(n)),$

read $f$ is big-O of $g$, to mean that there are a constant $C$ and a threshold $n_0$ with $f(n) \le C \cdot g(n)$ for every $n \ge n_0$. The constant $C$ absorbs machine-dependent factors, and the threshold sets small inputs aside. The bound need not be tight: $5n = O(n^{2})$ is a true statement, although $O(n)$ says more.

To find the tightest bound for a sum of terms, keep the fastest-growing term and drop its coefficient. The common growth rates fall into a single order, slowest first:

$1 \;<\; \log n \;<\; n \;<\; n \log n \;<\; n^{2} \;<\; 2^{n}.$

Ways to work on it

• Walkthrough. Dropping constants, the growth hierarchy, big-O as an upper bound.
• Practice. Tightest big-O of a polynomial.
• Hardest. n log n vs n², and exponential vs polynomial.

Not sure where to start? Take the ten-question placement test.