map / coding / complexity

Coding · principle 1 of 6

Complexity from first principles

Big-O is just counting how work grows with input — and at production scale, the difference between n and n² is the difference between fine and down.

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

↑ work doneinput size n →double n → O(n²) does 4× the workO(n²) — nested loopsO(n log n) — sortingO(n) — one passO(log n) — binary search
↑ work doneinput size n →n → 2n: 4× workO(n²) — nested loopsO(n log n) — sortingO(n) — one passO(log n) — binary search
Growth rate matters more than speed on small inputs.

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

  1. Naive: compare every pair — O(n²) time, far too slow at this size.
  2. 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.
  3. 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.
  4. If approximate answers are acceptable, a Bloom filter cuts memory a lot, with some false positives.