Recurrences and the master theorem
Describe divide-and-conquer cost with a recurrence and check it against its closed form.
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)1 0 0 2 2 2 4 8 8 8 24 24 16 64 64 1024 10240 10240
Explanation
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).
Three methods solve recurrences. The recursion tree adds the work at each level. Substitution guesses a bound and proves it by induction. The master theorem compares f(n) with n^(log_b a): if f grows polynomially slower the leaves dominate and T(n) = Θ(n^(log_b a)); if f matches it every level contributes equally and T(n) = Θ(n^(log_b a) · log n); if f grows polynomially faster, and a regularity condition holds, then T(n) = Θ(f(n)).
The example is the merge sort recurrence T(n) = 2T(n/2) + n with T(1) = 0. Here a = 2, b = 2, so n^(log_b a) = n, which matches f(n) = n. The middle case applies and gives Θ(n log n). For powers of two the exact value is n·log₂ n, and the program confirms that the recurrence and the formula agree.
Explore the dry run
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)Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Two subproblems of half the size, plus n to combine their answers. | t(2) = 2·t(1) + 2 = 2 | — | |
| For n = 8 the recursion tree has 3 levels, each costing 8, so t(8) = 24 = 8 × log₂ 8. | t(8) = 24 | 1 0 0 2 2 2 4 8 8 8 24 24 | |
| The recurrence matches n·log₂ n for every tested power of two, which is the Θ(n log n) the master theorem predicts. | t(8) = 24 | 1 0 0 2 2 2 4 8 8 8 24 24 16 64 64 1024 10240 10240 |
Cost and common mistakes
The recurrence solves to Θ(n log n). With memoization, t makes one real evaluation per distinct power of two it reaches, which is O(log n) evaluations.
- The closed form n·log₂ n is exact only for powers of two. For other n the recurrence needs floors and ceilings, though the Θ bound is unchanged.
- The master theorem does not cover every recurrence: it needs a constant a >= 1, a constant b > 1, and an f(n) comparable to a polynomial, so T(n) = 2T(n/2) + n/log n falls in a gap.
- lru_cache is used only to keep the recursion fast here; it does not change the recurrence being studied.
Try it yourself
Use the master theorem to classify T(n) = 4T(n/2) + n.
Reveal answer and reasoning
a = 4 and b = 2, so n^(log₂ 4) = n². Since f(n) = n grows polynomially slower than n², the leaves dominate and T(n) = Θ(n²).