Big O Notation
A notation for describing how an algorithm's runtime or memory usage grows as the input size increases.
Big O notation describes the asymptotic growth of a function: how an algorithm's running time or memory consumption scales as the input size n grows toward infinity. It captures the dominant term of the cost and discards constant factors and lower-order terms, because those depend on hardware and implementation details rather than on the shape of the growth curve. Writing "the algorithm runs in O(n log n) time" therefore communicates scaling behavior, not wall-clock seconds.
The common growth classes, from cheapest to most expensive, are:
| Class | Name | Example |
|---|---|---|
| O(1) | constant | array indexing by position |
| O(log n) | logarithmic | binary search |
| O(n) | linear | scanning an unsorted list |
| O(n log n) | linearithmic | merge sort, heap sort |
| O(n^2) | quadratic | nested loops over n items |
| O(2^n) | exponential | naive subset enumeration |
A 100-fold increase in input size turns an O(n) algorithm into roughly 100 times the work, but an O(n^2) algorithm into roughly 10,000 times the work. This is why asymptotic class matters more than micro-optimizations for large inputs: an efficient quadratic algorithm is usually slower than an inefficient linear one once the input is big enough.
Analysis normally distinguishes best, average, and worst cases. Quicksort, for example, is O(n log n) on average but O(n^2) in its worst case; the worst case is usually the guarantee that matters for systems software. Space complexity is described with the same notation and is often as important as time: an in-place sort uses O(1) extra space while merge sort needs O(n).
Big O is an upper bound; related notations such as Omega (a lower bound) and Theta (a tight bound) refine the description, but O is the one most commonly used in practice. Graph algorithms such as Dijkstra's shortest path are routinely described as O((V + E) log V), and SQL index lookups as O(log n) per probe.
Tags
algorithms complexity performance