Big-O in practice: amortised cost, worst cases and memory
What Big-O tells you on the job: the costs of common operations, amortised O(1), inputs that trigger the worst case, memory as a cost, and when to measure instead of guessing.
Big-O is a way to say how the cost grows as input grows, ignoring constant factors. On the job you use it to answer one question in design reviews: "what happens when this gets big?"
Common costs
| Cost | Feels like | Example |
|---|---|---|
| O(1) | Instant, whatever the size | Hash map lookup, array index |
| O(log n) | Barely grows: 1 million items, about 20 steps | Sorted-map lookup, binary search |
| O(n) | One pass | Scanning a list, reading a file |
| O(n log n) | A pass per level of sorting | Sorting |
| O(n²) | Every pair: 10,000 items is 100 million steps | Nested loops over the same list |
| O(2ⁿ) | Only works for tiny n | Trying every subset, naive backtracking |
The quick check: a loop inside a loop over the same data is O(n²). Fine for 100 items, a problem for 100,000. A lookup in an unsorted list inside a loop is the same thing in disguise.
Amortised O(1)
std::vector::push_back sometimes reallocates and copies every element, which is O(n). But it
grows the capacity by a factor each time, so over n pushes the total copying is O(n): O(1) per
push on average. That's amortised O(1).
When a ticket says "get and put must be O(1)", it rules out anything that scans: no searching a list for the least recently used entry. The usual answer is combining two structures, as in combining containers.
Worst-case inputs
Average-case performance is about honest users. Worst-case performance is about unlucky or hostile input:
- Regular expressions: a backtracking engine can take exponential time on a pattern like
(a+)+$and a long string ofas followed byb. That's a real outage cause (ReDoS). An NFA simulation is linear, always; see NFAs. - Hash maps: many keys with the same hash turn O(1) into O(n) per lookup.
- Recursion: deep nesting in input can overflow the stack; see depth limits.
If input comes from outside, ask "what's the worst input someone could send?" and write it into a test.
Memory is a cost too
Memory grows with input in the same ways, and it's often what actually fails:
- A per-client map that never removes idle clients grows forever. Prune entries that carry no information any more (a full token bucket is the same as a new one).
- An unbounded queue between a fast producer and a slow consumer eventually uses all memory. A bounded queue makes the producer wait instead (backpressure).
- A DP table of n × m integers may not fit; keep one row at a time.
- Reading a whole file into memory to process it line by line is O(file size) memory for no reason; stream it.
Measure
Big-O tells you which design can work. Which of two O(n) designs is faster is a question for a
benchmark: contiguous memory (std::vector) often beats node-based containers by a large
constant factor because of CPU caches. Build with optimisations on (-O2, Release mode) before
timing anything, and time realistic sizes, not ten elements.
Questions and answers
- What does amortised O(1) mean?
- That a long sequence of operations costs O(1) each on average, even if an occasional one is expensive. Appending to a dynamic array is the classic case: it sometimes copies everything to a bigger buffer, but rarely enough that the average stays constant.
- Do interviewers' Big-O questions matter in real jobs?
- The mindset does. On the job the question is 'what happens when this list has a million entries, or an attacker picks the input?'. Big-O answers that quickly; the constant factors you then measure.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Quickcart
A product cache for Quickcart
Put a least-recently-used cache in front of Quickcart's slow product service, with O(1) operations, statistics and live resizing.
- hash maps
- linked lists
- iterator stability
- amortised O(1)
Sieve Mail
A safe regex engine for Sieve Mail
Write the regular-expression engine behind Sieve Mail's filter rules: a parser, Thompson's NFA construction and a simulation that runs in linear time, so no rule can hang the mail servers.
- parsing
- automata
- Thompson's construction
- worst-case complexity
Gatekeep
Rate limiting for Gatekeep
Protect Gatekeep's customers from traffic floods with token buckets: exact integer refills, a testable clock, per-client limits and bounded memory.
- token buckets
- injected time
- integer arithmetic
- memory bounds
Mergebay
A diff engine for Mergebay
Compute minimal line diffs with the longest common subsequence, then render them as unified-diff hunks with context, exactly like the tools reviewers already know.
- dynamic programming
- LCS
- unified diff format
- edge cases
Read next
- Dynamic programming on real problems: diffs and edit distance
Dynamic programming explained with the problems it solves in real tools: the longest common subsequence behind diff, edit distance behind 'did you mean', and how to keep memory down.
- How to write a design doc: a short guide for junior developers
What a design document is for, a half-page template (components, data structures, trade-offs, open questions) and a worked example, before you write any code.