Explaining Complexity and Trade-offs

In an interview, getting the complexity right is not enough: you have to explain it. "It's O(n)" convinces far less than "n is this, and this operation happens this many times." This chapter covers how to explain complexity out loud, how to infer the target complexity from the input size, and how to discuss trade-offs between solutions.

Saying it out loud, in order

When you state a complexity, cover three things in turn.

1. Define the variables: say what you are counting, for example "n is the array length and m is the number of queries."
2. Name the dominant work: point at what happens most often, for example "the outer loop runs n times and each hash map lookup is O(1) on average."
3. State the space: give the extra memory beyond the input. For recursion, include the depth of the call stack.

For the longest-window-without-repeats solution from the previous chapter, it sounds like this: "n is the length of the string. right moves n times, and left only moves forward, so it moves at most n times as well. Each dictionary lookup and update is O(1) on average, so the time is O(n). The dictionary only holds distinct characters, so the space is O(min(n, σ))."

Inferring the target complexity from the input size

Constraints are a hint about the complexity the problem setter expects. A rough rule of thumb is that a compiled language handles on the order of 10⁸ simple operations per second, and Python handles tens of times fewer. Exact figures depend on the machine, so use only the order of magnitude.

One problem, three solutions

Here are three ways to answer "does the array contain two numbers that sum to the target?", followed by a comparison.

def has_pair_brute(nums: list[int], target: int) -> bool:
    # O(n^2) time, O(1) extra space
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False


def has_pair_sorted(nums: list[int], target: int) -> bool:
    # O(n log n) time; O(n) for the sorted copy (almost nothing extra if sorted in place)
    arr = sorted(nums)
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        total = arr[lo] + arr[hi]
        if total == target:
            return True
        lo, hi = (lo + 1, hi) if total < target else (lo, hi - 1)
    return False


def has_pair_hash(nums: list[int], target: int) -> bool:
    # O(n) average time, O(n) space
    seen: set[int] = set()
    for x in nums:
        if target - x in seen:
            return True
        seen.add(x)
    return False


for f in (has_pair_brute, has_pair_sorted, has_pair_hash):
    print(f.__name__, f([4, 7, 1, 9], 10), f([4, 7, 1, 9], 2))

If the interviewer asks "can you get the memory down to O(1)?", explain the trade-off of moving from the hash set to sort plus two pointers. To be precise, also mention that hash tables are O(1) on average but can degrade in the worst case because of collisions.

When nested loops are still O(n)

A sliding window has a while inside a for, which looks like O(n²), but the left pointer that the inner loop advances can increase at most n times over the entire run. Adding up the total work across all iterations like this is called amortized analysis. Counting the moves makes it concrete.

def count_moves(nums: list[int], target: int) -> tuple[int, int]:
    left = total = 0
    right_moves = left_moves = 0
    for value in nums:
        right_moves += 1
        total += value
        while total >= target:
            total -= nums[left]
            left += 1
            left_moves += 1
    return right_moves, left_moves


print(count_moves([1] * 1000, 3))  # (1000, 998): at most 2n moves combined

Hidden costs in Python

Even with a correct analysis, misjudging the cost of a language operation produces slow code. These are the usual suspects.

from collections import deque

items = list(range(10))

# list.pop(0) shifts every remaining element: O(n)
queue = deque(items)
first = queue.popleft()          # deque operations at either end are O(1)

# "in" is O(n) on a list but O(1) on average for a set
lookup = set(items)
print(7 in lookup)

# slicing copies: nums[i:j] costs O(j - i)
window_sum = sum(items[2:5])

# repeated string += can be slow; use join instead
text = "".join(str(x) for x in items)
print(first, window_sum, text)

Summary

Explain complexity by defining the variables, naming the dominant work and stating the extra space. Working backwards from the constraints to a target complexity narrows down the right pattern quickly. Most problems have several solutions that trade time for space, so be ready to explain why you chose one and what the alternatives are.