01 · Why it’s true
Big-O describes how the work a program does grows as its input grows, ignoring constant factors. For small inputs almost anything is fast; what matters at scale is the shape of the growth.
Doubling the input doubles the work of a linear scan, roughly quadruples the work of a nested loop (O(n²)), and adds just one step to a binary search (O(log n)). A nested loop that’s instant on a 1,000-line test file can take hours on a 10-million-line production log.
02 · Picture it
03 · In the interview
- Stating the time and memory complexity of your solution without being asked.
- Spotting accidental O(n²): a lookup in a list inside a loop, or repeated string concatenation in some languages.
- Considering memory too: can the input fit in RAM, or do you need to stream it?
04 · Practice question
“You need to find duplicate request IDs in a 50 GB log file. What’s your approach and its complexity?”
A strong answer covers
- Naive: compare every pair — O(n²) time, far too slow at this size.
- Stream the file line by line and keep a set of IDs seen so far: O(n) time, memory proportional to the number of unique IDs.
- If the unique IDs don’t fit in memory, partition by hash of the ID into smaller files, then dedupe each file, or sort externally and compare neighbours.
- If approximate answers are acceptable, a Bloom filter cuts memory a lot, with some false positives.