Big-O notation describes how the running time or memory usage of an algorithm grows as its input size increases, focusing on the dominant long-run trend while deliberately ignoring implementation details, constant factors, and small-scale behaviour. Originally developed in pure number theory, it became the standard language computer scientists use to compare and reason rigorously about algorithm efficiency.
Imagine two methods for finding a specific name in a phone book. Method 1: start at page 1, and check every single name in order until you find it. Method 2: open to the middle, see if your target comes before or after, and repeat this halving process. For a phone book with a million names, Method 1 might require checking up to a million names in the worst case, while Method 2 needs at most about 20 checks (since 2Β²β° is already over a million). Big-O notation is how computer scientists precisely describe and compare this dramatic difference.
Big-O deliberately ignores constant multipliers and lower-order details, focusing purely on how growth behaves for very large inputs. An algorithm that takes exactly 5n steps and one that takes exactly 3n+100 steps are both simply called O(n) β because for sufficiently large n, both are overwhelmingly dominated by their proportionality to n, and the specific constants become comparatively irrelevant to the algorithm's fundamental scaling behaviour.
f(n) = O(g(n)) means there exist positive constants C and nβ such that f(n) β€ CΒ·g(n) for all n β₯ nβ. In words: eventually (once n is large enough), f(n) is bounded above by some constant multiple of g(n). This precisely formalises the intuitive idea of "f doesn't grow faster than g, in the long run, up to a constant factor."
Big-O (O) describes an upper bound on growth. Big-Omega (Ξ©) describes a lower bound. Big-Theta (Ξ) describes a tight bound β both upper and lower simultaneously, meaning the algorithm's actual growth rate is precisely known, not merely bounded from one side. In casual usage, "Big-O" is often used loosely to mean any of these, but rigorous computer science texts distinguish them carefully.
An algorithm's running time can depend heavily on the specific input given, not just its size. Worst-case analysis (the most common standard) bounds the maximum possible time over all inputs of a given size β providing a reliable guarantee. Average-case analysis considers the expected time over some assumed distribution of typical inputs. Best-case analysis (least commonly emphasised, since it provides the weakest practical guarantee) considers the most favourable possible input.
Checking each of n items one at a time to find a target value: in the worst case (target is last, or absent entirely), this requires n comparisons β O(n). In the best case (target is first), it requires just 1 comparison β O(1). The standard, most commonly cited complexity for linear search is the worst-case bound, O(n).
| Algorithm | Average case | Worst case |
|---|---|---|
| Bubble sort | O(nΒ²) | O(nΒ²) |
| Merge sort | O(n log n) | O(n log n) |
| Quicksort | O(n log n) | O(nΒ²) |
Despite quicksort's theoretically worse worst-case bound, it is frequently used in practice because its average-case performance and constant-factor efficiency are excellent for typical real-world data.
Big-O notation was introduced not by computer scientists but by German number theorist Paul Bachmann in 1894, in a book on analytic number theory, studying the growth rates of number-theoretic functions. It was popularised and extended by Edmund Landau shortly afterward (hence sometimes called "Landau notation"), and only decades later, following Donald Knuth's influential adoption and systematisation of the notation in his seminal series The Art of Computer Programming (beginning 1968), did it become the near-universal standard language of computational complexity analysis in computer science.
Big-O notation is the essential language used to define formal complexity classes. A problem is in class P ("polynomial time") if it can be solved by an algorithm with worst-case running time O(nα΅) for some fixed constant k β considered the mathematical formalisation of "efficiently solvable." A problem is in class NP ("nondeterministic polynomial time") if a proposed solution can be verified in polynomial time, even if finding that solution in the first place might require far longer. The famous, unsolved P vs NP question (one of the seven Clay Millennium Prize Problems β see the Hilbert's 23 Problems entry) asks whether every problem whose solution can be quickly verified can also always be quickly solved β a question with profound implications for cryptography, optimization, and the theoretical limits of computation, remaining completely open as of 2026.
Some data structures have operations that are occasionally expensive but, on average across a long sequence of operations, remain cheap overall. Amortised analysis (formalised significantly by Robert Tarjan in the 1980s) rigorously bounds the average cost per operation across an entire sequence, even when individual operations vary considerably in cost β a classic example being a dynamically resizing array, where occasional expensive resize operations are more than compensated for by many subsequent cheap insertions, giving an amortised O(1) cost per insertion overall despite occasional O(n) worst-case individual operations.
Big-O analysis focuses purely on asymptotic (very large n) behaviour and deliberately ignores constant factors β meaning an algorithm with a smaller Big-O complexity class can nonetheless be genuinely slower in practice for realistic, moderate input sizes, if it carries a sufficiently large hidden constant factor or significant additional overhead. Real-world engineering practice must therefore always carefully balance rigorous asymptotic Big-O analysis against empirical, real-world benchmarking on realistic and representative data β Big-O provides essential theoretical guidance, but is deliberately not the complete practical picture on its own.