Complexity: reading it off, and deriving it

Complexity analysis is the shared vocabulary of a coding interview. You are expected to state a bound without being asked, justify it in a sentence, and know where the constant factors hiding inside the notation become the thing that actually matters.

Definition 1.1

The three bounds

Big-O, Omega and Theta, $f = O(g),\quad f = \Omega(g),\quad f = \Theta(g)$ — $O$ is an upper bound, $\Omega$ a lower bound, $\Theta$ both. In practice everyone says "big-O" and means $\Theta$ ; saying $\Theta$ when you mean it is a cheap way to sound precise, but do not correct an interviewer over it.

Structure	Access	Search	Insert	Delete
Dynamic array	$O(1)$	$O(n)$	$O(1)$ amortised	$O(n)$
Hash map	—	$O(1)$ average, $O(n)$ worst	$O(1)$ average	$O(1)$ average
Balanced BST	—	$O(\log n)$	$O(\log n)$	$O(\log n)$
Binary heap	$O(1)$ for the min	$O(n)$	$O(\log n)$	$O(\log n)$ for the min
Sorted array	$O(1)$	$O(\log n)$	$O(n)$	$O(n)$
Linked list	$O(n)$	$O(n)$	$O(1)$ given the node	$O(1)$ given the node

Table 1.2 · The operations you must know cold. The hash map row is the one that gets probed: average constant, worst case linear, and an interviewer may ask what makes the worst case happen.

Equation 1.3

The master theorem

Compare $f(n)$ with $n^{\log_b a}$ : whichever dominates gives the answer, and if they match you gain a $\log n$ .

T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)

$a$: Number of subproblems.
$n/b$: Size of each subproblem.
$f(n)$: Work done outside the recursive calls.

Example 1.4

Merge sort and binary search

Solve $T(n) = 2T(n/2) + O(n)$ and $T(n) = T(n/2) + O(1)$ .

Show the worked solutionHide the worked solution

Worked solution

Formula $\text{compare } f(n) \text{ with } n^{\log_b a}$
Substitute $\text{merge sort: } a = 2,\ b = 2 \Rightarrow n^{\log_2 2} = n$
Solve $f(n) = \Theta(n) = \Theta(n^{\log_b a}) \Rightarrow T(n) = \Theta(n\log n)$
$\text{binary search: } a=1,\ b=2 \Rightarrow n^{0} = 1 = f(n) \Rightarrow T(n) = \Theta(\log n)$
Answer $\Theta(n \log n) \text{ and } \Theta(\log n)$

Sanity check. Both land in the tied case, which is why both pick up a logarithm. It is worth recognising them by shape rather than re-deriving each time.

Figure 1.5 · The four curves worth recognising on sight. Drawn only to

n = 64

, where

n^2

has already left the frame. The gap that matters in practice is the narrow one between

n

and

n\log n

— most interview answers live there, and the factor of

\log n

is almost never what makes a solution too slow.

Proposition 1.6

Amortised is not average

A dynamic array’s push is $O(1)$ amortised: most pushes are constant and the occasional reallocation is linear, but the total across $n$ pushes is $O(n)$ . That is a worst-case guarantee on the *sequence*, unlike an average-case bound which is a statement about a distribution of inputs.

Holds when

Amortised: any sequence of $n$ operations costs $O(n)$ in total, guaranteed.
Average-case: the expected cost is low, but an adversary or an unlucky input can break it.

Why a trading system cares about the difference. Amortised bounds hide exactly the thing a latency-sensitive system is measured on. A vector that reallocates once every few thousand pushes has excellent throughput and a p99.9 that is far worse than its mean — and on a market-data path, the reallocation will land during the busiest microsecond of the day, because that is when the buffer fills. This is why hot-path code preallocates, and why interviewers at HRT or Jump follow "what is the complexity?" with "what is the tail latency?".

def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    """Return indices of two values summing to target."""
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None

Listing 1.7 · Complexity you can see. The nested-loop version is

O(n^2)

time and

O(1)

space. Trading a linear amount of memory for a linear-time algorithm is the single most common move in an interview, and saying so out loud is part of the answer. Time O(n) average · Space O(n).

Common trap. Quoting a bound without saying what $n$ is. "It is $O(n)$ " is meaningless when there are two inputs, a matrix, or a stream of events — and a candidate who says $O(n)$ for a problem that is really $O(nm)$ has not thought about the shape of the data. Instead. Name the variables first: " $O(n\log n)$ where $n$ is the number of orders, and the log comes from keeping the book sorted." That framing also makes the follow-up about a different data shape easy to answer.

Example 1.8

Two recurrences that look alike

Compare $T(n) = 2T(n/2) + n$ with $T(n) = 3T(n/2) + n$ . Why does one sort and the other not?

Show the worked solutionHide the worked solution

Worked solution

Formula $T(n) = aT(n/b) + n^{d}: \ \Theta(n^{d}\log n) \text{ if } a = b^{d}, \ \Theta(n^{\log_b a}) \text{ if } a > b^{d}$
Substitute $b = 2, \ d = 1$
Solve $a = 2 = b^{d} \Rightarrow \Theta(n\log n)$
$a = 3 > 2 \Rightarrow \Theta(n^{\log_2 3}) = \Theta(n^{1.585})$
Answer $\Theta(n\log n) \text{ against } \Theta(n^{1.585})$

Sanity check. The comparison is between the branching factor and the shrink factor raised to the work exponent. One extra subproblem turns a linearithmic algorithm into a superlinear one, which at $n = 10^6$ is a factor of about a hundred.

Largest n	Complexity that fits in about a second	Typical algorithm
$10$	$O(n!)$	All permutations
$20$	$O(2^n n)$	Subsets, bitmask DP
$500$	$O(n^3)$	Floyd–Warshall, interval DP
$5{,}000$	$O(n^2)$	Pairwise comparisons, 2D DP
$10^6$	$O(n \log n)$	Sorting, heaps, divide and conquer
$10^8$	$O(n)$	A single pass

Table 1.9 · What input size allows which complexity. For compiled code doing roughly

10^8

simple operations a second. Python is ten to a hundred times slower, so divide the sizes accordingly — or vectorise.

Example 1.10

Reading the constraint

An array has $10^5$ elements. Roughly how long do an $O(n^2)$ and an $O(n\log n)$ algorithm take at $10^8$ simple operations a second?

Show the worked solutionHide the worked solution

Worked solution

Formula $t \approx \frac{\text{operations}}{10^8\ \text{per second}}$
Substitute $n^2 = 10^{10};\quad n\log_2 n \approx 1.7 \times 10^6$
Solve $10^{10}/10^8 = 100 \text{ s}$
$1.7 \times 10^6/10^8 \approx 0.017 \text{ s}$
Answer $\text{about } 100 \text{ s against } 17 \text{ ms}$

Sanity check. The input size in a problem statement is a hint about the intended complexity. $n = 10^5$ says "not quadratic".

Example 1.11

A loop that doubles

What is the complexity of this, and how many times does the inner body run for $n = 1024$ ? for i in range(n): j = 1; while j < n: j *= 2

Show the worked solutionHide the worked solution

Worked solution

Formula $n \times \lceil\log_2 n\rceil$
Substitute $1024 \times 10$
Solve $= 10{,}240$
Answer $O(n\log n);\ 10{,}240 \text{ iterations}$

Sanity check. The inner loop does not depend on $i$ , so it is the same $\log_2 n$ steps every time. Loops that multiply or divide their counter are logarithmic; loops that add to it are linear.

Example 1.12

An uneven divide and conquer

Solve $T(n) = T(n/3) + T(2n/3) + n$ , the cost of a quicksort that always splits one-third to two-thirds.

Show the worked solutionHide the worked solution

Worked solution

Formula $\text{each level of the recursion tree costs at most } n$
Substitute $\text{depth} = \log_{3/2} n$
Solve $T(n) \le n\log_{3/2} n$
Answer $\Theta(n\log n)$

Sanity check. The master theorem does not apply to uneven splits, but the recursion tree does: every level sums to at most $n$ and there are logarithmically many. For $n = 10^6$ the deepest branch is about $34$ levels. Any constant-fraction split keeps quicksort at $n\log n$ .

Proposition 1.13

Recursion depth is space

A recursive function uses stack memory proportional to its maximum depth. A recursive DFS on a path of a million nodes needs a million frames, which overflows most default stacks — and Python’s default recursion limit is $1{,}000$ . Quote space as $O(\text{depth})$ and convert deep recursions to explicit stacks.

Holds when

Balanced recursions: $O(\log n)$ stack.
Recursion on a list or a degenerate tree: $O(n)$ stack.

When the constant beats the exponent. Asymptotic complexity ignores constants, and hardware does not. Scanning a contiguous array of $10{,}000$ items can beat a hash lookup, because the scan streams through cache while the hash jumps to random memory. Complexity picks the right family of algorithms; measurement picks within it.

Common trap — building a string in a loop. Appending to an immutable string inside a loop, s += piece, which can copy the whole string each time and turn a linear job quadratic. (CPython sometimes optimises this in place; relying on that is fragile.) Instead. Collect the pieces in a list and join once at the end: "".join(pieces) is linear.

What you need to know

Know the four-column table for the standard structures without thinking.
The master theorem compares $f(n)$ with $n^{\log_b a}$ ; the tied case gains a $\log n$ .
Amortised is a guarantee about a sequence; average-case is a statement about inputs.
Space complexity counts too, and trading space for time is the usual first improvement.
Always say what $n$ is.

Exercise 1.14

You need the $k$ largest of $n$ streaming values, with $k \ll n$ . What structure, and what complexity?

Show the answerHide the answer

A min-heap of size $k$ : push each value, pop when the heap exceeds $k$ . That is $O(n\log k)$ time and $O(k)$ space, against $O(n\log n)$ and $O(n)$ for sorting everything. The streaming constraint is what rules out sorting — you never hold all $n$ at once.

Exercise 1.15

Halving to one

How many iterations does while n > 1: n //= 2 make starting from $n = 10^6$ ?

Show the answerHide the answer

$19$ , which is $\lfloor\log_2 10^6\rfloor$ .

Exercise 1.16

Eight subproblems

What does $T(n) = 8T(n/2) + n^2$ solve to?

Show the answerHide the answer

$\Theta(n^3)$ : $n^{\log_2 8} = n^3$ dominates $n^2$ . It is the recursion of naive divide-and-conquer matrix multiplication — Strassen’s trick reduces the eight to seven.

In the interview

State the complexity before you are asked, and state it again if your solution changes. Volunteering "this is $O(n\log n)$ time and $O(n)$ space, and I think the log is removable with a hash map" turns a coding exercise into a design conversation, which is where the stronger signal is.

Hudson River Trading
Jump
Citadel Securities
Optiver

After this lesson you should be able to

What you need to know

In the interview