Big O is a mathematical notation that describes an asymptotic upper bound on the growth of a function, and in algorithms it is used to state how the running time or memory use of an algorithm grows as the input size n increases. Writing that an algorithm is O(n log n) means that, beyond some input size, its cost never exceeds a constant multiple of n log n.
Big O deliberately ignores constant factors and lower-order terms, so it compares the scaling behavior of algorithms rather than their speed on a particular machine. It is the shared vocabulary of programming interviews, library documentation and design reviews, and it belongs to a family of notations together with Big Omega and Big Theta.
The formal definition of Big O
Formally, a function f(n) is in O(g(n)) if there exist a positive constant c and a threshold n0 such that f(n) is at most c times g(n) for every n of at least n0. The definition describes a set of functions, so O(n) contains n, 5n + 20 and also log n, because each of them eventually stays below some multiple of n.
Two consequences follow directly. First, constants disappear: 3n squared and 0.01n squared are both O(n squared). Second, only the dominant term matters: n squared + 1000n + 50 is O(n squared), because the quadratic term outgrows the others as n becomes large. The notation therefore says nothing about small inputs, where a simpler algorithm with a worse Big O class may well run faster.
Because Big O is an upper bound, it is technically correct to call linear search O(n squared), although it is not useful. In practice engineers state the tightest known bound, and they often use Big O informally where a mathematician would write Big Theta.
Common complexity classes
A small set of growth classes covers most algorithms met in everyday software. The table orders them from the slowest-growing to the fastest-growing and shows what happens to the cost when the input doubles.
| Class | Name | Effect of doubling n | Typical example |
|---|---|---|---|
| O(1) | Constant | No change | Array access by index |
| O(log n) | Logarithmic | One extra step | Binary search in a sorted array |
| O(n) | Linear | Cost doubles | Scanning a list once |
| O(n log n) | Linearithmic | Slightly more than doubles | Merge sort, heapsort |
| O(n squared) | Quadratic | Cost quadruples | Comparing every pair of items |
| O(2 to the n) | Exponential | Cost squares | Brute-force subset search |
| O(n!) | Factorial | Explodes beyond small n | Trying every ordering of n cities |
The gap between classes grows dramatically. For one million items, a logarithmic algorithm needs about 20 steps, a linearithmic one about 20 million, and a quadratic one about a trillion. This is why moving an algorithm from quadratic to linearithmic usually matters far more than tuning its inner loop.
Big O, Big Omega and Big Theta
Big O is one of three related asymptotic notations, and the distinction between them is a frequent source of confusion. Big O bounds growth from above, Big Omega bounds it from below, and Big Theta states both at once. None of them is tied to a specific input case.
| Notation | Meaning | Informal reading | Example |
|---|---|---|---|
| Big O | Upper bound | Grows no faster than | Insertion sort is O(n squared) |
| Big Omega | Lower bound | Grows at least as fast as | Comparison sorting is Omega(n log n) |
| Big Theta | Tight bound | Grows exactly as fast as | Merge sort is Theta(n log n) |
| Little o | Strict upper bound | Grows strictly slower than | n is o(n squared) |
A common misconception equates Big O with the worst case and Big Omega with the best case. In fact, best, average and worst case are separate questions about which inputs are considered, and each case can be described with any of the three notations. Quicksort, for example, is Theta(n log n) on average but O(n squared) in its worst case.
How to derive Big O from code
Deriving Big O from code means counting how often the dominant operation runs as a function of n, then dropping constants and lower-order terms. A few composition rules handle most code.
- Sequential blocks add: O(n) followed by O(n squared) gives O(n squared).
- Nested loops multiply: a loop over n containing a loop over n is O(n squared).
- Halving the problem at each step, as binary search does, produces O(log n).
- Divide-and-conquer recursion is solved with recurrence relations, often through the master theorem.
- Library calls count: a membership test on a list is O(n), on a hash set it is average O(1).
Big O also applies to space complexity, the extra memory an algorithm needs. Merge sort runs in O(n log n) time but uses O(n) auxiliary space, whereas heapsort achieves the same time bound in O(1) extra space. For operations such as appending to a dynamic array, engineers quote amortized complexity, the average cost per operation over a long sequence, which is O(1) despite occasional O(n) resizes.
Limits and common misreadings
Big O is a model of growth, not a stopwatch, and treating it as a precise performance prediction leads to poor decisions. The table summarizes the most frequent misreadings.
| Misreading | Why it is wrong | Better practice |
|---|---|---|
| Lower Big O is always faster | Constants dominate for small n | Benchmark at realistic input sizes |
| Big O means worst case | Cases and bounds are independent | State the case and the bound explicitly |
| O(1) means instant | Constant can still be large | Measure hashing or network costs |
| Only time complexity matters | Memory can be the real limit | Analyze space complexity too |
| Hardware effects are irrelevant | Cache misses change real speed | Prefer contiguous data when bounds tie |
Insertion sort is quadratic yet beats merge sort on arrays of a few dozen elements, which is why production sorting routines such as Timsort switch to insertion sort for short runs. Big O should narrow the design space; profiling and benchmarks should make the final choice.
In everyday language
Big O answers a simple question: if the job gets bigger, how much more work does it take? Imagine finding a name in a phone book. Reading every page grows in step with the size of the book, while opening it in the middle and halving the search each time barely grows at all.
Big O ignores how fast a particular person or computer is. It only describes the shape of the growth. That makes it a quick way to tell whether a method will still work when ten customers turn into ten million.
Seen in the real world
An e-commerce team notices that the nightly job that flags duplicate customer records takes four minutes with 20,000 accounts but over six hours after the customer base grows to 250,000. Code review shows the job compares every record with every other record, an O(n squared) algorithm, so a twelvefold increase in data produced roughly a hundred-and-fifty-fold increase in work.
The engineers rewrite the job to build a normalized key for each record, such as a lowercase email address, and group records through a hash map, which makes the main pass O(n) on average. The job now finishes in under two minutes and scales comfortably as the customer base keeps growing.