Recurrences and the master theorem
Describe divide-and-conquer cost with a recurrence and check it against its closed form.
On this page
Recursion and growth rates.
- Describe divide-and-conquer cost with a recurrence and check it against its closed form.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
Code example
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
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
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 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
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²).