Complexity Analysis and the Cost of Operations

Every coding interview ends with the question "what is the time and space complexity?" A wrong answer here undoes good work, and a confident, justified answer is a strong signal. Complexity analysis is a small set of skills: counting how work grows with the input, recognising recursion patterns, understanding amortised cost, and knowing what the operations of your language's data structures actually cost. This chapter teaches each, with code you can run.

1. What big-O means, in practice

Big-O describes how the number of steps (or amount of memory) grows as the input size $n$ grows, ignoring constant factors and lower-order terms. We say an algorithm is $O(n^2)$ when its work grows no faster than a constant times $n^2$ for large $n$.

Two rules do most of the work:

1. Drop constants. $5n$ and $n/2$ are both $O(n)$. The constant matters in practice, and big-O deliberately ignores it, to describe growth.
2. Keep the dominant term. $n^2+100n+7$ is $O(n^2)$, because for large $n$ the square dominates.

Related notation, which you may be asked about:

• $\Omega$ (omega) is a lower bound: the work is at least this.
• $\Theta$ (theta) is a tight bound: the work is both at most and at least this, up to constants.
• In interviews, "big-O" is usually used loosely to mean the tight worst case. If it matters, say "worst case".

Average, worst and best case. A hash lookup is $O(1)$ on average and $O(n)$ in the worst case if everything collides. Quicksort is $O(n\log n)$ on average and $O(n^2)$ in the worst case. When the cases differ, state which you mean.

2. Counting loops

The simplest analysis is counting how many times the innermost statement runs.

One loop. Work proportional to the number of iterations.

def total(nums):
    s = 0
    for x in nums:        # n iterations
        s += x            # constant work
    return s              # O(n) time, O(1) space

assert total([1, 2, 3]) == 6

Nested loops. Multiply, when the inner loop count does not depend on the outer one.

def count_pairs(n):
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    return steps          # n * n

assert count_pairs(10) == 100   # O(n^2)

Dependent loops. When the inner bound depends on the outer variable, sum the series.

def count_triangle(n):
    steps = 0
    for i in range(n):
        for j in range(i):        # 0 + 1 + 2 + ... + (n-1)
            steps += 1
    return steps

assert count_triangle(10) == 45    # n(n-1)/2, which is O(n^2)

The sum $1+2+\cdots +n=n(n+1)/2$ is still $O(n^2)$. A loop pair like this often looks cheaper than $n^2$ and is not, in big-O terms.

Sequential loops. Add them, and keep the larger.

def two_passes(nums):
    best = max(nums)              # O(n)
    return [x - best for x in nums]   # O(n); total O(n) + O(n) = O(n)

assert two_passes([1, 5, 3]) == [-4, 0, -2]

Loops that shrink the problem geometrically are logarithmic.

def halvings(n):
    steps = 0
    while n > 1:
        n //= 2           # n, n/2, n/4, ... until 1
        steps += 1
    return steps

assert halvings(1024) == 10        # log2(1024); O(log n)

Multiplying or dividing the loop variable by a constant each iteration gives $O(\log n)$. Adding a constant gives $O(n)$.

A loop over $n$ with a logarithmic body is $O(n\log n)$, which is what you get from "for each element, do a binary search or heap operation".

3. Analysing recursion

For recursive functions, write the recurrence: how the work for size $n$ relates to the work for smaller sizes, plus the work done at this level.

One recursive call, constant extra work. $T(n)=T(n-1)+O(1)$, which is $O(n)$ calls.

def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)    # n calls, O(n) time, O(n) stack

assert fact(5) == 120

One call on half the input, constant extra work. $T(n)=T(n/2)+O(1)$, which is $O(\log n)$. This is binary search.

Two calls on half the input, linear extra work. $T(n)=2T(n/2)+O(n)$, which is $O(n\log n)$. This is merge sort: the tree of calls has $\log n$ levels, and each level does $O(n)$ total work.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])   # two half-size calls
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):                   # linear merge
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

assert merge_sort([5, 2, 9, 1, 5, 6]) == [1, 2, 5, 5, 6, 9]

Two calls on nearly the same size. $T(n)=2T(n-1)+O(1)$, which is $O(2^n)$. The naive Fibonacci is the classic example, and it is why memoisation matters.

calls = 0
def fib_naive(n):
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

assert fib_naive(15) == 610
assert calls == 1973               # grows roughly like 1.6^n

A shortcut for divide and conquer. For $T(n)=aT(n/b)+O(n^d)$, compare the work at the top level with the work at the bottom (the master theorem, in plain words):

• If the top level dominates ($d$ large compared with ${\log }_{b}a$): $O(n^d)$.
• If every level does equal work: $O(n^d\log n)$.
• If the leaves dominate: $O(n^{{\log }_{b}a})$.

You need this to explain results, not to derive them. Remember three cases: binary search $O(\log n)$, merge sort $O(n\log n)$, and a recursion that makes two calls and does little work is exponential in the depth.

A picture method. Draw the recursion tree. Count the nodes, and the work per node. The total is the sum over all nodes. For merge sort, $\log n$ levels each with total work $n$.

4. Space complexity

Space is the extra memory the algorithm uses, beyond the input, as a function of $n$.

• Variables and a fixed number of pointers: $O(1)$.
• A new list or dictionary that can grow to $n$ items: $O(n)$.
• A 2D table of $n\times m$: $O(nm)$.
• Recursion uses the call stack. A recursion that goes $n$ deep uses $O(n)$ stack space, even if it allocates nothing else. Binary search written recursively uses $O(\log n)$ stack, and the iterative version uses $O(1)$.

State whether you count the output in space. Many interviewers do not count the returned result, and it is polite to say which you mean.

Trade-offs. Many optimisations spend memory to save time: a hash map in two sum, a memo table in dynamic programming, a precomputed prefix sum. Say so explicitly: "this trades $O(n)$ space for $O(n)$ time".

In Python, a hidden source of space is slicing. a[:mid] creates a new list of that size, so the merge sort above uses $O(n\log n)$ total allocation, and a recursive binary search that slices the list is $O(n)$, not $O(\log n)$. Pass indexes instead of slices when it matters.

5. Amortised analysis

Some operations are usually cheap and occasionally expensive. Amortised cost is the average cost per operation over a sequence, which can be far below the worst single operation.

Dynamic array append. Appending to a Python list is usually constant, but when the capacity is full it allocates a bigger array and copies everything, which costs $O(n)$. If the capacity doubles each time, the copies cost $1+2+4+\cdots +n\approx 2n$ in total, spread over $n$ appends, so each append is $O(1)$ amortised.

The two-pointer and sliding window argument. A while loop nested inside a for loop looks like $O(n^2)$, but if the inner pointer only ever moves forward and never resets, the total movement of the inner pointer over the whole run is at most $n$, so the total work is $O(n)$.

def longest_unique_substring(s):
    last = {}
    best = start = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:   # shrink window from the left
            start = last[ch] + 1               # start only moves forward: at most n moves in total
        last[ch] = i
        best = max(best, i - start + 1)
    return best                                 # O(n) time overall, O(k) space for k distinct chars

assert longest_unique_substring("abcabcbb") == 3
assert longest_unique_substring("bbbbb") == 1
assert longest_unique_substring("pwwkew") == 3

The claim "each element is added once and removed once" is the standard way to justify linear time for such loops.

6. The cost of common operations

Interviews are often lost by a hidden cost. Know these for Python, and the equivalents in your language.

Consequences you should act on:

• Do not use a list as a queue. pop(0) is linear, so a BFS on a list is quadratic. Use deque.
• Do not test membership in a list inside a loop. Convert to a set first.
• Do not build a string with += in a loop for large outputs. Collect pieces in a list and "".join(...).
• Slicing copies. a[1:] in a recursive call makes the recursion $O(n^2)$.
• Sorting dominates many solutions. If a problem allows sorting first, the answer is at least $O(n\log n)$.

from collections import deque
import heapq

# O(1) at both ends
q = deque([1, 2, 3])
q.appendleft(0); q.append(4)
assert q.popleft() == 0 and q.pop() == 4

# O(log n) push and pop; O(1) peek at the smallest
h = []
for x in [5, 1, 4]:
    heapq.heappush(h, x)
assert heapq.heappop(h) == 1 and h[0] == 4

7. Hash map caveats

Hash tables give $O(1)$ average lookups, because a good hash function spreads keys evenly. The worst case is $O(n)$ when many keys collide. In interviews, state "$O(1)$ average" and move on, unless asked. Be ready to explain collisions (chaining or open addressing), resizing (the table doubles when it gets full, which is amortised $O(1)$ per insert), and why keys must be hashable (immutable): a list cannot be a dictionary key, but a tuple of numbers can.

8. Putting it together

Analyse a full function.

def has_duplicate_within_k(nums, k):
    window = set()
    for i, x in enumerate(nums):
        if x in window:                 # O(1) average
            return True
        window.add(x)                   # O(1) average
        if len(window) > k:
            window.remove(nums[i - k])  # O(1) average; each element removed at most once
    return False

assert has_duplicate_within_k([1, 2, 3, 1], 3) is True
assert has_duplicate_within_k([1, 2, 3, 1, 2, 3], 2) is False

Time: one loop of $n$ iterations, constant average work per iteration, so $O(n)$. Space: the window holds at most $k+1$ elements, so $O(\min (n,k))$. Notice how the answer comes from naming the cost of each operation, not from guessing.

9. Common mistakes

• Treating a nested loop as quadratic without checking whether the inner pointer resets, as in sliding window.
• Forgetting recursion stack space. A recursive DFS on a deep graph uses $O(\text{depth})$ memory, and in Python it can hit the recursion limit.
• Hidden $O(n)$ operations inside a loop: x in list, list.pop(0), slicing, string concatenation, list.index.
• Quoting average-case as worst-case, or the reverse, without saying which.
• Counting input size wrongly. For a graph, state complexity in terms of both $V$ and $E$. For a 2D grid, in terms of the number of cells ($R\times C$).
• Saying "$O(\log n)$" for anything that looks fast. Logarithmic needs the problem to shrink geometrically.
• Ignoring the cost of the output. Generating all subsets is $\Omega (2^n)$ simply because the output has that size.

10. Quick reference

11. Practice

1. State the time and space complexity of each function earlier in this chapter without looking, then check.
2. Write the recurrence for a recursive binary search and prove it is $O(\log n)$.
3. Rewrite merge_sort to pass indexes instead of slices. What is the new space complexity?
4. Explain why building a list with insert(0, x) $n$ times is $O(n^2)$ and what you would use instead.
5. For the code for i in range(n): for j in range(i, n): ..., count the iterations exactly and state the big-O.