Big-O Notation
Big-O notation describes how an algorithm's running time or space grows with input size, ignoring constants and lower-order terms.
Growth, not stopwatch time
Big-O notation classifies algorithms by how their resource use scales as the input grows, not by wall-clock time on a particular machine. Saying an algorithm is O(n^2) means its running time grows at most proportionally to the square of the input size for large n. Constants and lower-order terms are dropped because they do not affect the growth rate.
The formal idea
f(n) is O(g(n)) if beyond some input size there is a constant c such that f(n) is at most c times g(n). This upper-bounds the growth. Related notations bound it from below and both sides: Omega(g) is a lower bound, and Theta(g) means the function grows exactly like g, bounded above and below.
- O(1): constant — array index, hash lookup
- O(log n): logarithmic — binary search
- O(n): linear — a single scan
- O(n log n): merge sort, heapsort
- O(n^2): nested loops, simple sorts
- O(2^n): exponential — naive subset enumeration
Best, average, worst
An algorithm's cost can differ by input. Quicksort is O(n log n) on average but O(n^2) in the worst case. Worst-case bounds guarantee behaviour on any input; average-case bounds describe typical inputs but assume a distribution. Distinguishing them matters when a bad case is rare but catastrophic.
What Big-O hides
Big-O deliberately ignores constant factors, so an O(n) algorithm with a huge constant can be slower than an O(n log n) one for realistic input sizes. It also ignores memory hierarchy effects like caching. Asymptotic analysis is the right first cut for comparing algorithms, but final decisions should account for constants, input sizes, and actual measurement.