01 — Complexity

You already know Big O. What costs points is not the notation — it is being unable to say where the log comes from when asked, and confusing amortised with average.

Prereqs: none · Reading: 6 min · Cards: 10 · Reference: complexity table

The map

Complexity in an interview is not an analysis you perform at the end. It is a claim you make before you write anything, and then defend. That reframing is the whole topic: the interviewer does not want the number, they want to see that the number drove your design. Everything below exists to let you make that claim confidently and survive one follow-up question — because there is always exactly one follow-up, and it is almost always "why?".

The three ideas that carry it: growth rates tell you what the input size permits, amortised analysis explains the operations whose cost is uneven, and space complexity includes the recursion stack that everyone forgets.

What decides your score here

Stating the complexity before you code. This is the protocol step people skip, and skipping it turns your solution into a guess the interviewer has to evaluate on their own. Saying "this will be n log n because I sort first and then do a linear pass" before typing means everything you type is being read as an execution of a plan.

Being able to locate the log. Anyone can say n log n. Being asked "where does the log come from?" and answering "the search space halves at every step" or "there are log n levels each doing linear work" is the difference between a memorised bound and an understood one.

Knowing what the input size permits. Asking for the expected input size is the cheapest high-value question in the interview, because the answer decides the solution. Around twenty, exponential is fine and you should say so rather than agonising. At a million, anything quadratic is dead on arrival and you know it before writing a line.

Amortised analysis, which is where the gap usually is

Amortised means the average cost per operation across a whole sequence, guaranteed in the worst case. It is not the average over inputs, and confusing the two is a common way to sound less precise than you are.

Appending to a dynamic array is the canonical case. Most appends are constant. Occasionally the array is full, so it allocates a bigger one and copies everything, which is linear. But that only happens once every n appends, and because the capacity doubles, the total copying across n appends sums to less than 2n. Divide by n and each append costs a constant.

The doubling is doing all the work in that argument. If the array grew by a fixed hundred elements instead, you would copy on every hundredth append, and those copies would sum to n²/2 — which is linear per append, not constant. The multiplicative growth factor is what buys the amortised constant, and being able to say that is the difference between reciting a fact and explaining one.

The same reasoning covers three other things you will meet: a monotonic stack is linear despite its inner while loop, because each element is pushed once and popped at most once. Union-find with path compression is near-constant for the same kind of reason. And a hash table that resizes by doubling is amortised constant for exactly the argument above.

Contrast that with quicksort, which is n log n on average — an expectation over inputs, with a quadratic worst case still lurking. Amortised admits no such escape: there is no input sequence that makes appending quadratic.

Space, including the part people forget

Count the auxiliary structures, then count the recursion stack. The stack is the omission that gets caught: a recursive DFS on a graph is O(V) of stack in the worst case, and quicksort is only O(log n) of stack if you deliberately recurse into the smaller partition and loop on the larger one.

One Python-specific trap worth having ready: sorted() builds a new list, so it is not in place despite how it reads. .sort() is.

The Python costs that are actually performance bugs

These four are what an interviewer looks for in Python code, because each silently multiplies your complexity by n. Membership testing on a list is linear, so x in lst inside a loop is quadratic — use a set. Popping or inserting at index zero is linear because everything shifts, which turns a BFS into O(n²) — use a deque. And string concatenation in a loop is quadratic, because strings are immutable and each += copies everything so far — collect the parts and join once.

The full cost table lives in the reference card. Do not memorise it; memorise these four, because these are the ones that appear in code you write under pressure.

Say it

Cover the right-hand side. Answer out loud, in English, then check. These are scheduled by drill.py conceitos — this section is the preview, not the practice.

Now do this

Three problems, in this order. The exercise is not the code — it is writing down the complexity you predict before you start, then checking whether you were right.

1. Two Sum — 10 min. Predict the brute force and the optimised bound before writing either.
2. Daily Temperatures — 20 min. Predict, then explain out loud why the inner while does not make it quadratic.
3. Kth Largest Element in an Array — 20 min. Give two solutions with different bounds and say which you would ship.

Stop when you can state a bound before coding three times in a row without hesitating, and defend each with one sentence about where the log or the n comes from.