Complexity: Recurrences and the Master Theorem

Quickselect's worst case, T(n) = T(n - 1) + O(n) = O(n^2), does not fit the theorem because the subproblem shrinks by one element instead of a constant factor.

Karatsuba: three products instead of four

Split two numbers at m digits: x = x1 * 10^m + x0 and y = y1 * 10^m + y0. Then x * y = z2 * 10^(2m) + z1 * 10^m + z0, with z2 = x1 * y1, z0 = x0 * y0 and z1 = x1 * y0 + x0 * y1. Computing z1 directly needs two more products, giving 4T(n/2) and therefore O(n^2), no better than schoolbook multiplication. Karatsuba's trick is z1 = (x1 + x0) * (y1 + y0) - z2 - z0, which needs only one extra product. Three subproblems give O(n^log2(3)), about O(n^1.585).

def karatsuba(x, y):
    """Product of two non-negative integers with three recursive products."""
    if x < 10 or y < 10:
        return x * y
    m = max(len(str(x)), len(str(y))) // 2
    x1, x0 = divmod(x, 10 ** m)
    y1, y0 = divmod(y, 10 ** m)
    z2 = karatsuba(x1, y1)
    z0 = karatsuba(x0, y0)
    z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0
    return z2 * 10 ** (2 * m) + z1 * 10 ** m + z0

print(karatsuba(1234, 5678) == 1234 * 5678)  # True

Closest pair: why the strip is cheap

To find the closest pair among n points, sort them by x, split at the median x, and solve both halves to get d, the smaller of the two best distances. A closer pair must cross the dividing line, so both of its points lie in a strip of width 2d around it. Sort the strip by y; within that order each point only needs to be compared with a constant number of following points (at most 7), because more points than that cannot fit in a d by 2d box while staying d apart. The combine step is O(n) if the halves are merged by y as in merge sort, so T(n) = 2T(n/2) + O(n) = O(n log n). Re-sorting the strip at every level instead costs O(n log^2 n).

Counting the work

Counting operations is a quick way to check an analysis:

def count_mults(e):
    """Multiplications done by recursive fast power for exponent e."""
    if e == 0:
        return 0
    return count_mults(e // 2) + (2 if e % 2 else 1)

for e in (10, 1000, 10**6, 10**18):
    print(e, "naive:", max(e - 1, 0), "fast:", count_mults(e))

For e = 10^18 the naive method needs about 10^18 multiplications; fast power needs fewer than 120.

Comparison with alternatives

Space matters too. Merge sort needs O(n) extra memory for merging, while recursion depth is O(log n) for balanced splits. Quickselect works in place but can recurse O(n) deep with bad pivots, which is why the loop form in the previous chapters is safer in Python.

Summary

• Write T(n) = a * T(n/b) + f(n) and compare f(n) with n^log_b(a).
• Equal cost on every level adds a log n factor; otherwise the leaves or the root dominate.
• Karatsuba wins by turning four subproblems into three.
• Shrinking by a constant factor matters: shrinking by one element gives quadratic time.