Big-O without the maths

Big-O answers exactly one question: when the input gets bigger, how much worse does it get? Not “how fast is it” — a quadratic algorithm can beat a linear one on small inputs all day — but how the cost scales. Double the input: O(n) doubles, O(n²) quadruples, O(log n) barely notices, O(2ⁿ) ends your afternoon. That’s the whole idea; everything else is fluency.

The ladder, with felt sizes

Attach a feeling to each rung, using n = 1,000,000 as the yardstick:

• O(1) — one step. A hash lookup. n could be anything.
• O(log n) — ~20 steps. Binary search through a million. Halving is absurdly powerful, and “log” in a bound almost always means something halves each round.
• O(n) — a million steps. One honest look at everything. For most problems this is the floor: you can’t answer questions about data you never read.
• O(n log n) — ~20 million. “Do a log thing for each element”, or “split in half, handle both, combine”. Sorting’s home.
• O(n²) — a trillion. Every pair. Fine at n = 5,000, fatal at a million. The gap between this rung and the last is where most timeouts live.
• O(2ⁿ) — every subset. Dead past n ≈ 25 and no hardware upgrade will ever save it: adding one element doubles the work, which is a statement about the algorithm, not the machine.

Reading growth off the code’s shape

You rarely derive complexity from formulas; you read it from structure. A loop over the input: n. A loop inside a loop, both over the input: n². A loop whose variable halves (or doubles toward n): log n. A recursion that splits the problem in two and touches everything at each level — merge sort’s shape — is levels × per-level: log n × n. A recursion that branches without shrinking much — “try every choice at every step” — is exponential, and you should hear alarm bells.

Two refinements make this reading trustworthy. First, inner loops that shrink still usually count full price: bubble sort’s inner loop runs n−1, n−2, … 1 times, and that sum is n(n−1)/2 — the ½ vanishes in the notation but the n² does not. Triangle-shaped double loops are quadratic, full stop. Second, name what n is — for a graph, cost is usually V + E, not “n”; for two strings, n·m. Half of all complexity mistakes are really ambiguity about which quantity was growing.

The traps

Hidden costs inside innocent lines. list.pop(0) in Python is O(n) — it shifts everything. String concatenation in a loop rebuilds the string each pass: quadratic. array.includes inside a loop: quadratic. The syntax is one line; the cost is a loop you didn’t write. When totting up a loop body, price every operation, not every line — this single habit catches more real slowdowns than any formula.

“Amortized” is a different promise. A dynamic array’s append is O(1) amortized: most appends are cheap, and the occasional resize (copy everything) averages out over a long sequence. Averaged over the sequence — not guaranteed per call. For a latency-sensitive path, one O(n) resize at the wrong moment is real even though the amortized claim is true. Hash tables carry the same asterisk: O(1) expected, with adversarial or unlucky inputs degrading toward O(n).

Space counts too, and recursion is space. Every recursive call holds a stack frame; recursing n deep is O(n) memory, plus the crash risk when n outruns the stack limit. Merge sort quietly spends O(n) on its buffer while its time bound gets all the attention. When someone asks for complexity, giving time and space unprompted is the cheapest way to sound like you’ve done this before.

Constants are invisible and occasionally decisive. Big-O deliberately erases multipliers, and usually that’s right — but it’s why insertion sort beats merge sort under ~30 elements (every hybrid sort exploits this), why heap sort loses to quicksort in practice (cache-hostile memory jumps), and why a “worse” algorithm with sequential access can outrun a “better” one that pointer-chases. The notation ranks growth; wall clocks also charge for memory layout.

Best, worst, and expected — say which

One algorithm, three legitimate numbers: quicksort is n log n on average, n² against adversarial pivots; hash lookups are O(1) expected, O(n) in pathological collision storms. Unqualified, “what’s the complexity?” conventionally means worst case — so if you answer with the average, say the word “average” and then give the worst case too, plus what triggers it. That two-sentence pattern (“average X, worst Y when Z”) is the complete answer interviewers are fishing for, and the live counters on every visualization on this site exist so you can watch X and Y diverge — run bubble sort’s sorted preset against its reversed one and the difference stops being notation.