fundamentals
Big-O & Complexity
A mental model for reasoning about how an algorithm's time and memory usage scale with input size — the foundation of every performance conversation in engineering.
What Is Big-O?
Big-O notation describes an upper bound on how an algorithm's cost grows as input size n grows. It captures the dominant term and drops constants so you can compare algorithms on the same scale.
| Notation | Name | Common examples |
|---|---|---|
| O(1) | Constant | Hash map lookup, array index |
| O(log n) | Logarithmic | Binary search, balanced tree ops |
| O(n) | Linear | Single pass through an array |
| O(n log n) | Log-linear | Merge sort, heap sort |
| O(n²) | Quadratic | Nested loops over same input |
| O(2ⁿ) | Exponential | Naive subset enumeration |
How to Reason About It in Practice
When you see a loop, ask: how many iterations, and what does each cost?
- One loop over
nitems → O(n) - Two nested loops over
nitems → O(n²) - Halving the input each step → O(log n)
- Building all subsets → O(2ⁿ)
Space complexity follows the same logic applied to memory allocations.
Memoization Pays Off
Naive recursive Fibonacci is O(2ⁿ) because it recomputes overlapping subproblems. Memoization collapses that to O(n).
Without @cache this call tree is exponential. With it, each unique n is computed once and stored.
When Big-O Misleads You
Big-O describes growth, not absolute speed — and that gap matters. It deliberately drops constants and lower-order terms, so an O(n) algorithm with heavy per-element work can lose to an O(n²) one when n is small. Real data is often small. Profile before "optimizing" a quadratic that only ever sees fifty items.
It also says nothing about constant factors that dominate in practice: cache locality, allocation, and I/O frequently outweigh the asymptotic class. Treat Big-O as the first filter on a design, not the last word — the right answer is "O(n log n), and I measured it on realistic input."