How It Works: From Counting Operations to the Master Theorem

Finding a complexity is more mechanical than it looks. Pick a basic operation, follow the structure of the code (sequence, loop, nesting, recursion) to write its count as a function of n, then keep only the largest term. This chapter walks through that process on small examples.

Step 1: pick a basic operation

A basic operation takes constant time regardless of input size: a comparison, an addition, an array index, an assignment. Counting one core action is usually enough, such as comparisons for sorting or elements inspected for searching.

Watch out for one-liners that are not basic operations. In Python, x in some_list scans the list (O(n)), sorted(items) is O(n log n), and s + t copies both strings.

Step 2: count by structure

Let us count the comparisons in this function:

def count_pairs_with_sum(items, target):
    count = 0
    n = len(items)
    for i in range(n):              # i = 0 .. n-1
        for j in range(i + 1, n):   # n-1-i iterations
            if items[i] + items[j] == target:
                count += 1
    return count

The inner loop runs n-1 times when i is 0, n-2 times when i is 1, and 0 times at the end. The total is (n-1) + (n-2) + ... + 0 = n(n-1)/2, which expands to n²/2 - n/2. Dropping constants and the lower-order term gives Θ(n²). Counting for small n matches the formula:

Roughly four times the work for twice the input is the signature of n².

Step 3: halving gives log n

Binary search halves the remaining range of a sorted list at every step. Going 16 → 8 → 4 → 2 → 1 takes four halvings, and even 1,024 elements need only about ten. "How many times can n be halved before reaching 1" is exactly log₂ n.

def halving_steps(n):
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

for n in (16, 1_024, 1_000_000):
    print(n, halving_steps(n))
# 16 4
# 1024 10
# 1000000 19

The base of the logarithm only changes a constant factor (log₂ n = log₁₀ n / log₁₀ 2), so we just write O(log n). An outer loop of n iterations around a halving loop gives O(n log n).

Step 4: recursion becomes a recurrence

For a recursive function, write a recurrence from "how many calls, on how much smaller input" plus "the work done outside those calls".

def merge_sort(items):
    if len(items) <= 1:                 # base case: T(1) = O(1)
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])      # T(n/2)
    right = merge_sort(items[mid:])     # T(n/2)
    merged, i, j = [], 0, 0             # merge: O(n)
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

The recurrence is T(n) = 2T(n/2) + O(n). In the recursion tree every level merges n elements in total and there are log n levels, so the whole sort is O(n log n).

The master theorem in plain words

The master theorem handles recurrences of the form T(n) = a·T(n/b) + f(n): solve a subproblems of size n/b, and spend f(n) splitting and combining. The trick is to compare the work done by the leaves, n^(log_b a), with the work at the root, f(n).

• Leaves win (f is polynomially smaller): T(n) = Θ(n^(log_b a))
• A tie (same order): every level does similar work, so multiply by the number of levels: T(n) = Θ(n^(log_b a) · log n)
• Root wins (f is polynomially larger and satisfies a regularity condition): T(n) = Θ(f(n))

The theorem does not apply when the size shrinks by subtraction instead of a ratio, as in naive recursive Fibonacci, T(n) = T(n-1) + T(n-2) + O(1). There the number of calls grows like 1.618^n, which is exponential.

Summary

• Pick a basic operation; add for sequences, multiply for nesting, use a logarithm for halving.
• Count the cost of built-in one-liners such as in list, sorting and string concatenation.
• Write recursion as a recurrence; for aT(n/b) + f(n), the master theorem compares the leaves with the root.