Big-O notation
The conceptWhy an app that's fast with 100 items can freeze with a million
Big-O notation describes how the work a program does grows as its input grows. It doesn't measure seconds. It describes the shape of the growth: how the step count changes when the input gets 10 or 1,000 times bigger.
Reading each of n names once takes about n steps: O(n), or linear. Comparing every name with every other takes about n × n steps: O(n²), or quadratic. At a million names, that's a million steps versus a trillion.
To get the Big-O, keep the fastest-growing term and drop constants: 3n² + 5n + 2 steps is O(n²), since n² dwarfs the rest at large n. Big-O usually describes the worst case, an upper bound.
What it’s forDefines what it means for a step count to grow no faster than a simpler function.
f(n) is O(g(n)) if f(n) ≤ c · g(n) for all n ≥ n₀
- f(n)
- the real number of steps for an input of size n, e.g. 3n² + 5n + 2
- g(n)
- the simple growth shape we compare against, e.g. n²
- c
- a fixed multiplier we are allowed to choose, e.g. 4
- n₀
- the input size from which the bound must hold, e.g. 6
What it givesA guarantee that, past some size, the work never grows faster than g(n) times a constant.
- f(n) = 3n² + 5n + 2, try c = 4, g(n) = n²
- n = 6: f = 108 + 30 + 2 = 140 ≤ 4 × 36 = 144 ✓
- At n = 5: 102 > 100, so it holds from n₀ = 6 on: f(n) is O(n²)