Complexity & Big-O

Before you can compare two solutions, you need a language for “how expensive is this?” that ignores the noise of a particular laptop, language, or input. That language is Big-O notation: a way to describe how an algorithm’s cost grows as its input grows.

The key word is grows. Big-O throws away constants and lower-order terms because, as the input gets large, only the fastest-growing term matters. A loop that does 3n + 50 operations is simply O(n) — double the input and you roughly double the work.

Watch the curves diverge

The whole reason we obsess over Big-O is this picture. At small inputs, an O(n²) algorithm can look perfectly fine. Drag the slider and watch what happens as the input grows — the quadratic curve leaves everything else behind.

Notice that O(log n) is almost flat: even at n = 40 it has barely moved. That flatness is why binary search and balanced trees feel like magic. Meanwhile O(n²) is the shape of a nested loop, and it is the complexity you most often need to avoid in an interview.

The complexities you must recognize on sight

Time is not the only cost

Every algorithm also has a space complexity — the extra memory it needs beyond the input. A recursive function that goes n levels deep uses O(n) stack space. Building a hash set of every element uses O(n) memory. Interviewers love the time/space trade-off, because “make it faster by using more memory” (or the reverse) is the single most common optimization in real systems.

Rule of thumb: state your solution’s time and space complexity out loud, unprompted. It signals that you think about cost by default.

How to reason about it quickly

1. Count the loops. Independent loops add; nested loops over the same input multiply. Two separate passes are O(n) + O(n) = O(n). A loop inside a loop is O(n²).
2. Find the halving. If each step throws away a constant fraction of the remaining work, you have a logarithm.
3. Recursion → recurrence. “Do O(n) work, then two half-size calls” is the merge-sort recurrence and resolves to O(n log n).

Keep this lens on as you go through the rest of the module — every pattern that follows is really just a trick to move a solution down this table.

Pattern recognition

Variations

Worked problems

These are not about inventing an algorithm. They are about reading code like an interviewer reads it: count the dominant work, then state the space trade-off.

def first_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return x
        seen.add(x)
    return None

def first_duplicate(nums):
    seen = set()          # up to n elements
    for x in nums:        # at most n iterations
        if x in seen:     # average O(1)
            return x
        seen.add(x)       # average O(1)
    return None

def count_pairs(nums):
    total = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] < nums[j]:
                total += 1
    return total

def pair_iterations(n):
    return n * (n - 1) // 2

def mark_blocked(blocked_ids, incoming_ids):
    blocked = set(blocked_ids)
    return [user_id in blocked for user_id in incoming_ids]