How It Works: From Counting Operations to the Master Theorem

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.