Big-O Notation
A way to describe how an algorithm's cost grows with input size, keeping only the dominant term and ignoring constants.
Big-O Notation
Big-O notation answers the question that matters when an algorithm meets real data: how does its cost grow as the input gets bigger? It deliberately throws away everything inessential — constant factors, low-order terms, the speed of your particular machine — and keeps only the shape of the growth. We say a routine runs in O(n^2) time if, for large enough n, its step count is bounded by some constant times n^2.
Why ignore constants? Because they are a property of the hardware and implementation, not the algorithm. A faster CPU shifts a constant; it cannot rescue an algorithm whose work explodes as 2^n. For large inputs, growth rate dominates everything else.
The growth zoo
A handful of growth rates cover almost everything you will meet. The gulf between them is enormous — and it only widens as n grows.
The same picture in words, from gentlest to most ruinous:
- O(1) — constant. Array lookup, hash insert. Input size is irrelevant.
- O(\log n) — logarithmic. Halve the search space each step: binary search, balanced trees.
- O(n) — linear. Look at each item once.
- O(n \log n) — linearithmic. The best comparison sorts (merge sort, heap sort).
- O(n^2) — quadratic. Every pair: nested loops, naive sorts.
- O(2^n), O(n!) — exponential / factorial. Try every subset or ordering. Hopeless past small n.
Best, worst, and average
Big-O usually describes the worst case — the guarantee that cost never exceeds this bound. Sometimes the typical case differs sharply: quicksort is O(n^2) in the worst case but O(n \log n) on average, which is why it is fast in practice. Sibling notations sharpen the picture: \Omega is a lower bound (no faster than), and \Theta pins growth from both sides (exactly this rate).
This vocabulary is what lets us rank algorithms independently of hardware — the foundation for classifying problems by difficulty in Complexity Classes, and for appreciating why an O((V+E)\log V) method like Dijkstra's Algorithm scales gracefully to enormous graphs.