Recurrences and the master theorem

A recursive algorithm's running time is naturally written as a recurrence: an equation that gives T(n) in terms of T on smaller inputs. A divide-and-conquer algorithm that splits a problem into a subproblems of size n/b and spends f(n) to divide and combine has the form T(n) = a·T(n/b) + f(n).

from functools import lru_cache


@lru_cache(maxsize=None)
def t(n):
    if n == 1:
        return 0
    return 2 * t(n // 2) + n


def closed_form(n):
    return n * (n.bit_length() - 1)


for n in (1, 2, 4, 8, 16, 1024):
    print(n, t(n), closed_form(n))
    assert t(n) == closed_form(n)