Big O — Notation for Algorithm Performance
Table of contents
Big O — Notation for Algorithm Performance
The question "is this code fast?" has different answers depending on environment, hardware, and input. So computer science describes — as a function — how time (or memory) grows as input size grows. That notation is Big O. This article covers Big O's origin, common growth rates, time and space complexity, and what it means and where it falls short in practice.
1. About Big O
The notation first appeared in 1894 in German mathematician Paul Bachmann's book Analytische Zahlentheorie, and was systematized by Edmund Landau in 1909 — hence also called "Landau symbols". In computer science, Donald Knuth's 1976 paper "Big Omicron and big Omega and big Theta" cemented the conventions.
Sister notations:
| Notation | Meaning |
|---|---|
O(f) |
Upper bound — at least this fast (actual run is at most c·f(n)) |
Ω(f) |
Lower bound — at least this slow |
Θ(f) |
Tight bound — upper and lower agree |
o(f) |
Strict upper bound — actually faster |
In everyday talk almost everything is called Big O, and when the meaning is the tight bound, read it as Θ.
2. Common growth rates
| Notation | Name | Going from 10K to 1M |
|---|---|---|
| O(1) | constant | unchanged |
| O(log n) | logarithmic | about 1.3× |
| O(n) | linear | 100× |
| O(n log n) | linearithmic | about 130× |
| O(n²) | quadratic | 10,000× |
| O(n³) | cubic | 1,000,000× |
| O(2ⁿ) | exponential | effectively forever |
| O(n!) | factorial | effectively forever |
Same data, same job — the algorithm choice can mean a millionfold difference.
3. Graph
time
│ O(2ⁿ)
│ O(n²)
│ ╱
│ ╱
│ ╱
│ ╱ O(n log n)
│ ╱ O(n)
│ ╱ ────
│ ╱ ────
│──── O(log n)
│═══════════════════════════ O(1)
└───────────────────────────── → input size n
4. Drop the constants
Big O looks at behavior as input grows large enough. Constant multipliers and lower-order terms are dropped:
3n + 5 → O(n)
n² + n + 7 → O(n²)
1000n → O(n)
0.001 · 2ⁿ → O(2ⁿ)
This simplification keeps conversations short, but in practice constants can matter. "O(n) with a constant of 1000" vs "O(n log n) with a constant of 1" — for small inputs the latter can win.
5. Best · average · worst
The same algorithm takes different time on different inputs:
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) |
| Binary search (sorted) | O(1) | O(log n) | O(log n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) — already-sorted input, etc. |
| Merge sort | O(n log n) | O(n log n) | O(n log n) |
| Hash table lookup | O(1) | O(1) | O(n) — collision blowup |
In operations, decisions are often based on the worst rather than the average. If even one user hits the worst case, the screen freezes.
6. Space complexity
Beyond time, the same notation also describes how memory grows with input. When recursion is deep, call-stack memory grows alongside, so deciding by time alone risks OOM:
| Algorithm | Time | Space |
|---|---|---|
| Merge sort | O(n log n) | O(n) — auxiliary array |
| Quick sort (in-place) | O(n log n) | O(log n) — call stack |
| Dynamic programming | varies | O(n) ~ O(n²) — memoization table |
| Memory-efficient sort (heap sort) | O(n log n) | O(1) |
7. Other paths
Other ways to express performance:
- Wall-clock time — actual elapsed time (seconds). Depends on environment.
- CPU time — CPU occupancy time.
- Operation count — number of comparisons, memory accesses.
- Benchmark — compare two implementations in the same environment.
The gap between theory and measurement is often the issue. CPU cache, branch prediction, SIMD, and memory locality cause big differences in places Big O cannot capture. Operational decisions ultimately come from measurement.
8. Estimating Big O from code
// O(1) — independent of input
function first(arr) { return arr[0]; }
// O(n) — single pass
function sum(arr) {
let s = 0;
for (const x of arr) s += x;
return s;
}
// O(n²) — nested loop
function pairs(arr) {
const out = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
out.push([arr[i], arr[j]]);
}
}
return out;
}
// O(log n) — halving each step
function binarySearch(sorted, target) {
let lo = 0, hi = sorted.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (sorted[mid] === target) return mid;
if (sorted[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// O(n log n) — sort then a pass
function uniqueSorted(arr) {
return [...new Set(arr)].sort();
}
Common heuristics:
- A single simple loop → O(n)
- Nested loops → product of depths. Two levels → O(n²)
- A structure that halves each iteration → O(log n)
- Sort once and work on top → O(n log n)
- All subsets → O(2ⁿ)
- All permutations → O(n!)
9. Common stumbles
Unfounded optimization — Knuth's 1974 line "premature optimization is the root of all evil" gets cited often. Beware tangling code without measurement.
Constant trap — even at O(n), if each step is very expensive (disk I/O), an algorithm of the same order with smaller constants beats it.
Small input vs large input — at n around 100, all orders are close. The differences only show up at n in the millions.
Memory first — a cache-friendly O(n²) can outrun a cache-unfriendly O(n log n) on small to medium inputs.
Ignoring amortized — dynamic array push is occasionally O(n) but averages O(1). Called amortized. Judging it "slow" from one expensive step is a mistake.
Theory vs measurement gap — when orders are similar, deciding by measurement is the honest path.
Closing thoughts
Big O is a tool that describes growth in one line as input grows. For everyday data structure choice, that one line nearly settles the answer. But operational decisions ultimately come from measurement — theory and measurement diverge often. "premature optimization is the root of all evil" lives here.
Next
- design-patterns
- oop-vs-functional
We refer to Donald Knuth Big Omicron and big Omega and big Theta (1976) · The Art of Computer Programming · Knuth Structured Programming with go to Statements (1974) · Introduction to Algorithms (CLRS) · MIT 6.006 · Big-O Cheat Sheet · VisuAlgo · Wikipedia Big O notation.