Big-O and the Complexity Questions Interviews Ask

3 min read

Quant-dev and research-coding screens rarely demand exotic algorithms. They demand that you know the cost of what you write — and can lower it one notch when asked "can you do better?" That skill is 90% fluency with the growth-rate ladder.

The ladder

$O(1) \;<\; O(\log n) \;<\; O(n) \;<\; O(n \log n) \;<\; O(n^2) \;<\; O(2^n)$

Attach a mental picture to each: hash lookup (1); binary search (log n — 30 steps searches a billion items); one scan (n); the best comparison sorts (n log n); all-pairs / nested loops (n²); brute-force subsets (2ⁿ, dead past n ≈ 25). Big-O ignores constants and lower-order terms — it describes scaling, which is what matters when $n$ is a day of tick data.

The three moves that answer most questions

1. Trade memory for time with a hash map. The canonical example — "find two numbers in an array summing to K" — goes from $O(n^2)$ (check all pairs) to $O(n)$ : one pass, storing seen values in a set, asking K − x in seen at each step. A remarkable fraction of "can you do better?" answers are exactly this move.

2. Sort first, then exploit order. Sorting costs $O(n \log n)$ and buys binary search, two-pointer scans, and easy duplicates/median logic. If the input is already sorted and your answer doesn't use that — you've missed the intended solution. ("Find if any two intervals overlap": sort by start, one scan.)

3. Amortize. An operation can be occasionally expensive but cheap on average: a dynamic array that doubles on overflow does $O(1)$ amortized appends despite occasional $O(n)$ copies. Knowing the word — and the doubling example — covers the standard probe.

Costs of what you already use

For a Python-flavored screen, know your containers cold:

Operation	list	dict / set
index / lookup by key	$O(1)$	$O(1)$ average
membership `x in c`	$O(n)$	$O(1)$ average
append	$O(1)$ amortized	—
insert/delete at front	$O(n)$	—

The single most common performance bug interviewers plant: x in some_list inside a loop — $O(n^2)$ total, fixed by one set() conversion. Say the fix and the reason.

Quant-flavored classics

Running median of a stream (position marking, real-time analytics): two heaps — max-heap of the lower half, min-heap of the upper — $O(\log n)$ per insert, $O(1)$ median. The heap pair is the canonical "streaming" data structure and worth rehearsing.
Moving average / rolling sum over a window: don't re-sum the window ( $O(nk)$ ); keep a running sum, add the new element, subtract the departing one — $O(n)$ total. Same trick powers rolling vol and any sliding-window statistic.
First repeated element in a tick stream: set, one pass, $O(n)$ — the two-sum move again.
"Your backtest is slow." The productive diagnostic order: complexity first (is something accidentally quadratic — like list-membership or string concatenation in a loop?), then vectorization, then constants. Naming that order is a strong systems-thinking signal.

The interview version

The dialogue is always the same shape: you give a working brute force ("that's $O(n^2)$ "), the interviewer asks for better, you apply move 1 or 2 and state the new cost, and — the part candidates skip — you mention the space cost you paid ( $O(n)$ for the hash set) and any assumptions (hashable elements, average-case behavior). Explicitly narrating time and space, best and worst case, is what separates "solved it" from "hired."