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))