A recurrence says T(n) in terms of smaller T. Merge sort: split in half (2 T(n/2)) plus linear merge (+ n). Unrolling shows Θ(n log n).

Goal

Unroll T(n) = 2T(n/2) + n on powers of two and print the total.

Base and recurrence

def T(n):
    if n <= 1:
        return 1
    return 2 * T(n // 2) + n

for n in (1, 2, 4, 8, 16):
    print(n, T(n))

Compare to n * log2(n):

def log2(n):
    k = 0
    x = n
    while x > 1:
        x //= 2
        k += 1
    return k

def T(n):
    if n <= 1:
        return 1
    return 2 * T(n // 2) + n

for n in (2, 4, 8, 16):
    print(n, "T", T(n), "n log n", n * log2(n))

They track. Each of log n levels does n work.

A slower split

def T_unbalanced(n):
    if n <= 1:
        return 1
    return T_unbalanced(n - 1) + n

for n in (4, 8, 12):
    print(n, T_unbalanced(n))

T(n) = T(n-1) + n is Θ(n²) (1+2+…+n). Quicksort’s worst partition looks like this.

Tip

You do not need the Master Theorem in this course. Unroll a power of two and look at the table.