Big-O Notation & Complexity Analysis
Big-O notation describes how an algorithm's cost grows as its input grows. It's the language engineers use to reason about performance independent of hardware, language, or constant factors: an O(n) algorithm's work scales linearly with input size; an O(n²) one quadratically. Knowing the difference is what lets you predict, before running anything, whether code will be instant or unusable at scale.
The point isn't precise timing — it's scaling behavior. A function that's fine on 100 items might melt down on 100,000, and Big-O tells you which. Paired with data-structure choices, it's the core of writing code that holds up under real load.
TL;DR
- Big-O describes how cost grows with input size, ignoring constants.
- Common classes (best→worst): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n).
- Analyze both time and space complexity.
- Consider best/average/worst case — and amortized cost.
Quick Example
Nesting a loop inside a loop turns O(n) into O(n²) — the classic scaling trap:
The Growth Classes
💡 The jump from O(n log n) to O(n²) is where things break at scale. If your input can grow large, getting off O(n²) is usually the single biggest win.
Reading Big-O
Big-O keeps only the dominant term and drops constants: O(2n + 5) is O(n); O(n² + n) is O(n²). It describes an upper bound on growth — how the algorithm behaves as n → ∞ — not exact operation counts. That's why a "slower" Big-O can still win on small inputs (constants and overhead matter there), but the higher-growth algorithm always loses eventually as n grows.
Time vs Space
- Time complexity — how the number of operations grows with input.
- Space complexity — how much extra memory grows with input.
There's often a tradeoff: you can spend memory to save time (e.g. a hash table or memoization turning an O(n²) scan into O(n)) or save memory at the cost of time. Analyze both — an algorithm that's fast but allocates O(n²) memory can fail just as surely as a slow one.
Best, Average & Worst Case
The same algorithm can have different complexity depending on the input:
- Worst case — the guarantee you can rely on (e.g. quicksort O(n²) on a bad pivot).
- Average case — typical behavior (quicksort O(n log n) in practice).
- Best case — the lucky path (often less useful to design around).
Amortized analysis captures the average over a sequence — e.g. a dynamic array's append is O(1) amortized even though an occasional resize is O(n).
Best Practices
- Know the Big-O of your hot path — especially loops and the operations inside them.
- Watch for hidden costs — a method call inside a loop may itself be O(n), making the loop O(n²).
- Prefer the right data structure — an O(1) lookup can collapse an O(n²) algorithm to O(n).
- Design around the worst case when correctness/latency guarantees matter.
- Don't micro-optimize constants before fixing the growth class — algorithmic wins dominate.
Common Mistakes
The hidden nested loop
Optimizing constants instead of complexity
FAQ
Why ignore constants and lower-order terms?
Because Big-O describes scaling, and as input grows the dominant term swamps everything else — at n = 1,000,000, the difference between n² and n² + 5n + 100 is irrelevant, but the difference between n² and n log n is enormous. Dropping constants also makes the analysis hardware- and language-independent. The caveat: for small or fixed-size inputs, constants and overhead do matter, so Big-O is about asymptotic behavior, not a promise about tiny n.
What's the difference between time and space complexity?
Time complexity measures how the number of operations grows with input size; space complexity measures how much extra memory grows. They're often in tension — memoization or a hash index spends memory (space) to save repeated work (time), while a streaming algorithm saves memory at the cost of more passes. Analyze both, because an algorithm that's fast but uses O(n²) memory can run out of RAM just as an O(n²)-time one runs out of patience.
Should I always pick the algorithm with the best Big-O?
Not always. Big-O describes large-n behavior, so for small or bounded inputs a "worse" Big-O with low constants can be faster (e.g. insertion sort beats quicksort on tiny arrays). Also weigh worst-case guarantees, memory use, and code simplicity. Use Big-O to avoid algorithms that won't scale, then let real measurements settle close calls. The big wins come from avoiding quadratic/exponential blowups, not from chasing marginal asymptotic differences.
What is amortized complexity?
Amortized complexity is the average cost per operation across a sequence of operations, even when individual operations vary. The classic example is appending to a dynamic array: most appends are O(1), but occasionally the array doubles its capacity (an O(n) copy). Averaged over many appends, each is O(1) amortized. It's the honest way to describe structures whose costs are usually cheap but occasionally expensive, without pessimistically labeling every operation by its rare worst case.
Related Topics
- Core Data Structures — Complexity of each structure's operations
- Sorting Algorithms — O(n log n) vs O(n²)
- Searching Algorithms — O(log n) binary search
- Dynamic Programming — Trading space for time
- Performance Optimization — Applying this in practice