Big-O notation
A way to describe how an algorithm's runtime or memory grows as input grows. O(1) is constant, O(n) is linear, O(n²) is quadratic, O(log n) is logarithmic. Big-O tells you if your code will scale — O(n²) on a million items is a billion operations.
- When comparing algorithm efficiency.
- When deciding if code will scale.
- Micro-optimization (measure real performance instead).
- Small inputs where constants dominate.
Definition
Big-O describes the upper bound of growth rate as input size n approaches infinity. O(1) doesn't grow, O(log n) grows slowly, O(n) linearly, O(n log n) slightly worse, O(n²) quadratically, O(2ⁿ) exponentially. Drop constants and lower-order terms.
Why it exists
To compare algorithms independent of hardware and constants, focusing on how they scale. An O(n) algorithm will always beat O(n²) for large enough n.
How it works
Count the dominant operations as a function of input size. Express the growth rate, dropping constants (O(2n) → O(n)) and lower terms (O(n² + n) → O(n²)). Common: O(1) hash lookup, O(log n) binary search, O(n) scan, O(n log n) sort, O(n²) nested loop.
Scaling limits
Big-O hides constants — an O(n) with a huge constant can lose to O(n log n) for practical inputs. It describes asymptotic behavior, not real-world speed.
Cost shape
Free.
Alternatives
- Benchmarking — Real numbers but hardware-specific.
Failure modes
- Ignoring constants when they matter.
- Optimizing Big-O before measuring.
- Confusing best/average/worst case.