Big-O and Reading Complexity Off Code

Complexity answers one question: when the input gets bigger, how much more work do you do? Everything else in the notation is bookkeeping around that question.

It matters in an interview for a plain reason. Almost every coding question has a slow answer that is easy to find and a fast answer that is the point of the question. You cannot tell which one you have written, or explain why the fast one is better, unless you can read its cost. This lesson gives you that skill for both time and memory, without any mathematics beyond multiplying and halving.

Start with running times, not the notation

Assume a machine does roughly 100 million simple operations per second. That is a rough working number for compiled languages such as C++ or Java, and it is the figure competitive programmers use when they size a solution. Now look at what different growth rates cost at that speed.

The table is most of the lesson. An n² solution and an n log n solution are both fine at n = 1,000. At n = 100,000 one returns before you blink and the other takes longer than the interview.

Python is slower per step. A plain Python loop manages roughly 10 to 30 million simple steps per second on a laptop, so divide the budget by five or ten. The shape of the table does not change: the n² column still explodes at the same place, just sooner.

Now the notation

Two rules produce every complexity you will write in an interview:

• Drop the constants. 3n + 50 is O(n). Doubling n still roughly doubles the work, and that is all the notation records.
• Keep only the fastest-growing term. n² + 1000n is O(n²). At n = 10,000 the n² term is 100,000,000 and the 1000n term is 10,000,000 — ten times smaller, and the gap widens forever.

Unless a lesson says otherwise, complexity in this course means the worst case: the slowest input of size n. When the average and the worst case differ, as with hash maps, we say both.

Where dropping constants misleads you

Big-O describes behaviour as n grows without limit. At small n the constants can win. An O(n²) insertion sort with a very tight inner loop beats an O(n log n) merge sort on a few dozen elements, which is why real sorting libraries use insertion sort for short runs. Python's built-in sort does exactly this for runs of up to 64 elements.

The ladder, from worst to best, is worth memorising:

O(n!) → O(2ⁿ) → O(n³) → O(n²) → O(n log n) → O(n) → O(log n) → O(1)

Almost every pattern in this course exists to move a solution one or two rungs up that ladder. Two pointers turns O(n²) into O(n). Binary search turns O(n) into O(log n). Memoisation turns O(2ⁿ) into O(n²) or better.

Reading time complexity off code

There is a mechanical procedure. You do not have to feel your way to an answer.

1. Find every loop — for each one, ask how many times it runs in terms of n.
2. Multiply nested loops, add sequential ones — and when you add, the bigger term wins.
3. Look inside every library call — x in my_list is a loop you did not write.
4. For recursion, count branches and depth — total calls are roughly branches ^ depth.

Now six snippets, in order of subtlety. Work out each one before you read the answer.

Snippet 1 — one loop

1def total(numbers: list[int]) -> int:2    """Sum of all values."""3    running_sum = 04    for value in numbers:          # runs n times5        running_sum += value       # O(1) work inside6    return running_sum

n iterations times constant work is O(n).

Snippet 2 — nested loops

1def has_duplicate_pair(numbers: list[int]) -> bool:2    """True if any value appears twice."""3    for i in range(len(numbers)):                # n times4        for j in range(i + 1, len(numbers)):     # up to n - 1 times5            if numbers[i] == numbers[j]:6                return True7    return False

The inner loop shrinks, so the true count is n(n − 1) / 2 comparisons. Drop the constant 1/2 and the smaller term, and you get O(n²). A shrinking inner loop does not save you a complexity class. At n = 100,000 this is still about 5 billion comparisons.

Snippet 3 — sequential, not nested

1def spread(numbers: list[int]) -> int:2    """Largest value minus smallest value."""3    largest = max(numbers)      # O(n)4    smallest = min(numbers)     # O(n)5    return largest - smallest

O(n) + O(n) = O(2n) = O(n). Two passes are still linear. Candidates sometimes squeeze two passes into one to "optimise" — it does not change the class, and it often makes the code harder to read.

Snippet 4 — halving

1def count_halvings(n: int) -> int:2    """How many times n can be halved before it reaches 1."""3    steps = 04    while n > 1:5        n //= 2          # the remaining work halves each time6        steps += 17    return steps

Starting at 1,000,000 this returns 19. Starting at 1,000,000,000 it returns 29. Halving gives O(log n), and in this course log means base 2 unless we say otherwise. The base does not matter inside Big-O, because logs in different bases differ only by a constant factor.

Snippet 5 — the hidden loop

1def unique_values(numbers: list[int]) -> list[int]:2    """First copy of each value, in order."""3    seen = []4    for value in numbers:        # n times5        if value not in seen:    # scans the list `seen`: up to n comparisons6            seen.append(value)7    return seen

This looks like one loop. But value not in seen on a list is a linear scan, so the real cost is O(n²). Keep a set for the membership test (and the list only for the output order), and each check becomes average O(1), making the whole function O(n). On 20,000 distinct values the list version took about 2 seconds on our test machine; the set version took about 1 millisecond. This one line is the whole argument of the Hash Maps and Sets section.

Snippet 6 — branching recursion

1def fib(n: int) -> int:2    """n-th Fibonacci number, computed the slow way."""3    if n <= 1:4        return n5    return fib(n - 1) + fib(n - 2)   # two calls per level

Each call makes two more, and the depth is up to n, so 2ⁿ calls is a safe upper bound: O(2ⁿ). The exact count grows a little slower, about 1.6ⁿ, because the n − 2 branch is shorter. It is still exponential. fib(30) makes 2,692,537 calls and fib(40) makes about 331 million. Compare a recursion that makes one call and halves its input: one branch, depth log n, so O(log n).

Costs hidden inside common operations

Snippet 5 is the most common misread in real interviews, so learn the usual hiding places in Python.

Space complexity: what counts

Space complexity is the extra memory your solution needs beyond the input it was handed.

The convention exists because the caller already allocated the input. Counting it would make every solution O(n), and the measure would tell you nothing. Here are two ways to reverse a list, measured honestly:

1def reverse_with_copy(numbers: list[int]) -> list[int]:2    """O(n) auxiliary space: builds a whole new list."""3    return numbers[::-1]456def reverse_in_place(numbers: list[int]) -> None:7    """O(1) auxiliary space: two indices, whatever the length."""8    left, right = 0, len(numbers) - 19    while left < right:10        numbers[left], numbers[right] = numbers[right], numbers[left]11        left += 112        right -= 1

The second uses two integers whether the list holds ten items or ten million. That is O(1).

The cost everyone forgets: the call stack

Every pending recursive call holds a stack frame: its parameters, its local variables and where to return to. The frame stays alive until the call returns.

1def sum_list(node: "Node | None") -> int:2    """Recursive sum of a linked list."""3    if node is None:4        return 05    return node.value + sum_list(node.next)

No list or dictionary is allocated here, yet this is O(n) space. On a list of 100,000 nodes there would be 100,000 frames waiting at once. Python stops long before that: its default recursion limit is 1,000 frames, after which it raises RecursionError. The iterative version, with one while loop and a running total, is O(1) space and has no limit.

Notice what the chart shows. O(1) and O(log n) look almost the same at this scale — a binary search over a billion items holds only about 30 frames. O(n) is a straight line and usually acceptable. O(n²) memory leaves the chart early, which is why a two-dimensional table over a large input is almost always the wrong answer.

What counts in practice

Saying it in the interview

Interviewers ask for complexity the moment you finish coding, and they want both numbers with a reason. Use a fixed sentence: "This is O(n) time because each element is visited once, and O(k) extra space for the map of at most k distinct keys."