Sums, recurrences and the Master theorem

Separate recursive call count, subproblem size and nonrecursive work. Merge sort obeys T(n)=2T(n/2)+Θ(n). Each level of its recursion tree contains Θ(n) work and the tree has about log₂n levels, giving Θ(n log n).

The Master theorem applies to balanced recurrences of the form aT(n/b)+f(n). Compare f(n) with n^(log_b a), and check the case assumptions. Unequal splits, n−1 reductions and irregular costs require expansion, substitution or induction rather than forcing the theorem.

T(n)=T(n−1)+n expands into a triangular sum. T(n)=T(n/2)+1 has constant work per level. State base cases such as T(1)=Θ(1). Floors and ceilings often preserve asymptotic bounds, but executable boundary handling still matters.

def halving_depth(n):
    if n < 1:
        raise ValueError("n must be positive")
    depth = 0
    while n > 1:
        n //= 2
        depth += 1
    return depth
assert halving_depth(8) == 3