Solving Recurrences and the Master Theorem: short notes (Algorithms)

Revision mode

Introduction

The running time of a recursive algorithm is naturally described by a recurrence: an equation that gives $T(n)$ in terms of $T$ on smaller inputs. Merge sort splits an array into two halves, sorts each and merges in linear time, so $T(n) = 2T(n/2) + \Theta(n)$ . Solving the recurrence means finding a closed-form asymptotic bound, here $T(n) = \Theta(n \lg n)$ .

This note covers the four standard methods: substitution, recursion trees, the master theorem, and unrolling for subtract-type recurrences, together with change of variables and the cases where the master theorem does not apply.

Prerequisites

Asymptotic Notation: $O$ , $\Omega$ , $\Theta$ , polynomial versus logarithmic growth.
Recurrence Relations: exact solution of linear recurrences such as $a_n = a_{n-1} + a_{n-2}$ .
Geometric series: $\sum_{i=0}^{k} r^i$ is $\Theta(1)$ for $r < 1$ , $k + 1$ for $r = 1$ , and $\Theta(r^k)$ for $r > 1$ .

Core concepts

Conventions

$T(n)$ is a running time, so it is positive, and $T(n) = \Theta(1)$ for all $n$ below some constant. The base case is usually omitted because it changes the solution by at most a constant factor.
Floors and ceilings ( $T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil)$ ) are usually dropped; for the recurrences treated in this note they do not change the asymptotic answer (CLRS 3e, Section 4.6 justifies this for the master recurrence).
$\lg n = \log_2 n$ . The critical exponent of the master recurrence is $\log_b a$ ; for example $\log_2 7 \approx 2.807$ and $\log_4 3 \approx 0.793$ .

Method 1: substitution (guess and prove by induction)

Guess the form of the solution (from a recursion tree or experience).
Prove it by induction on $n$ , finding constants that make the inductive step work.

Example: $T(n) = 2T(\lfloor n/2 \rfloor) + n$ . Guess $T(n) \le c\,n \lg n$ . Assume it for $\lfloor n/2 \rfloor$ . Then

T(n) \le 2c \lfloor n/2 \rfloor \lg \lfloor n/2 \rfloor + n \le c\,n \lg(n/2) + n = c\,n \lg n - c\,n + n \le c\,n \lg n \quad \text{for } c \ge 1.

The base case is handled by choosing $n_0$ and $c$ large enough (start the induction at $n = 2, 3$ rather than $n = 1$ , since $\lg 1 = 0$ ).

Two pitfalls.

The inductive step must give exactly the hypothesis. Trying to prove $T(n) = O(n)$ for the same recurrence gives $T(n) \le cn + n$ , which is not $\le cn$ for any constant $c$ . Writing " $cn + n = O(n)$ , done" is a wrong proof.
Subtract a lower-order term when the guess is right but the induction fails. For $T(n) = 2T(n/2) + 1$ , the guess $T(n) \le cn$ gives $cn + 1$ , which fails. The stronger guess $T(n) \le cn - d$ gives $2(c n/2 - d) + 1 = cn - 2d + 1 \le cn - d$ whenever $d \ge 1$ . So $T(n) = O(n)$ .

Method 2: the recursion tree

Draw the tree of recursive calls. Each node is labelled with the non-recursive cost of its call; sum each level, then sum the levels.

For $T(n) = aT(n/b) + f(n)$ :

Level $i$ (root is level 0) has $a^i$ nodes, each of size $n/b^i$ , costing $a^i f(n/b^i)$ in total.
The tree has $\log_b n$ levels below the root, and the bottom level has $a^{\log_b n} = n^{\log_b a}$ leaves, each costing $\Theta(1)$ .

T(n) = \Theta\big(n^{\log_b a}\big) + \sum_{i=0}^{\log_b n - 1} a^i f\!\left(\frac{n}{b^i}\right).

Example: $T(n) = 2T(n/2) + cn$ . Every level costs $cn$ ( $2^i$ nodes of cost $cn/2^i$ ), there are $\lg n + 1$ levels, so $T(n) = cn \lg n + \Theta(n) = \Theta(n \lg n)$ .

Recursion tree for T(n) = 2T(n/2) + cn — Figure 1. The recursion tree of $T(n) = 2T(n/2) + cn$ for $n = 8$ : levels 0 to 3, node costs $cn$ , $cn/2$ , $cn/4$ , $c$ , and a level total of $cn$ on the right of every level; total $cn(\lg n + 1)$ .

Unequal splits. For $T(n) = T(n/3) + T(2n/3) + cn$ , each full level still costs $cn$ , but the tree is lopsided: the shortest root-to-leaf path has length $\log_3 n$ and the longest $\log_{3/2} n$ . Summing gives at most $cn \log_{3/2} n$ and at least $cn \log_3 n$ , so $T(n) = \Theta(n \lg n)$ . The master theorem does not apply here, because the subproblems have different sizes.

Recursion tree with unequal splits — Figure 2. The recursion tree of $T(n) = T(n/3) + T(2n/3) + cn$ : the first three levels each cost $cn$ ; the leftmost path ends after $\log_3 n$ levels and the rightmost after $\log_{3/2} n$ levels.

A useful rule follows from the same argument. If $T(n) = T(\alpha_1 n) + \dots + T(\alpha_k n) + \Theta(n)$ with fixed constants $0 < \alpha_j < 1$ , suitable integer rounding and a terminating constant-size base case, then the costs of full levels form a geometric series with ratio $s = \alpha_1 + \dots + \alpha_k$ .

Partial levels cannot exceed the corresponding full-level cost. With shrinking fractions, the shallowest and deepest leaves both have depth $\Theta(\lg n)$ ; for $s=1$ , the full levels give the $\Omega(n\lg n)$ lower bound, and all levels together give $O(n\lg n)$ . For $s<1$ , summing the full-level upper bounds gives $O(n)$ , while the root gives $\Omega(n)$ .

$s = \sum \alpha_j$	Solution
$s < 1$	$\Theta(n)$ , for example $T(n) = T(n/2) + T(n/4) + T(n/8) + n$ ( $s = 7/8$ )
$s = 1$	$\Theta(n \lg n)$ , for example $T(n) = T(n/3) + T(2n/3) + n$

For $s > 1$ the answer is a power $n^p$ with $p > 1$ defined by $\sum \alpha_j^p = 1$ ; for equal splits this is the master theorem's $n^{\log_b a}$ .

Method 3: the master theorem

Master theorem (CLRS 3e, Section 4.5). Let $a \ge 1$ and $b > 1$ be constants, let $f(n)$ be an asymptotically positive function, and let $T(n)$ be defined on the non-negative integers by

T(n) = a\,T(n/b) + f(n),

where $n/b$ may be read as $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$ . Compare $f(n)$ with the watershed function $n^{\log_b a}$ :

If $f(n) = O(n^{\log_b a - \varepsilon})$ for some constant $\varepsilon > 0$ , then $T(n) = \Theta(n^{\log_b a})$ .
If $f(n) = \Theta(n^{\log_b a})$ , then $T(n) = \Theta(n^{\log_b a} \lg n)$ .
If $f(n) = \Omega(n^{\log_b a + \varepsilon})$ for some constant $\varepsilon > 0$ , and if $a\,f(n/b) \le c\,f(n)$ for some constant $c < 1$ and all sufficiently large $n$ (the regularity condition), then $T(n) = \Theta(f(n))$ .

Interpretation through the recursion tree: in case 1 the leaves dominate (level costs grow geometrically downwards); in case 2 all $\log_b n + 1$ levels cost the same; in case 3 the root dominates (level costs shrink geometrically).

Per-level costs in the three master-theorem cases — Figure 3. Level totals for three recurrences with $a = b = 2$ or $a = 8, b = 2$ . Case 1, $8T(n/2) + n^2$ : $n^2, 2n^2, 4n^2, \ldots$ (leaves dominate). Case 2, $2T(n/2) + n$ : $n, n, n, \ldots$ (all equal). Case 3, $2T(n/2) + n^2$ : $n^2, n^2/2, n^2/4, \ldots$ (root dominates).

Notes on the conditions.

"Polynomially smaller" (case 1) and "polynomially larger" (case 3) mean by a factor $n^{\varepsilon}$ . A logarithmic factor is not enough: $n \lg n$ is larger than $n$ but not polynomially larger.
For polynomial $f(n) = \Theta(n^k)$ with $k > \log_b a$ , regularity holds automatically: $a (n/b)^k = (a/b^k) n^k$ and $a/b^k < 1$ . So the condition matters only for unusual $f$ .
The regularity condition can fail. Take $a = 1$ , $b = 2$ , $f(n) = n(2 - \cos n)$ . Then $f(n) \ge n = \Omega(n^{0 + 1})$ , so the first part of case 3 holds, but for infinitely many even $n$ ( $n = 6, 18, 32, \ldots$ ) $f(n/2) > f(n)$ , and the ratio $f(n/2)/f(n)$ comes arbitrarily close to $3/2$ . No constant $c < 1$ works, and case 3 cannot be used.

Extended case 2 (CLRS 3e, Exercise 4.6-2). If $f(n) = \Theta(n^{\log_b a} \lg^k n)$ for a constant $k \ge 0$ , then $T(n) = \Theta(n^{\log_b a} \lg^{k+1} n)$ . Case 2 is the special case $k = 0$ . This covers $T(n) = 2T(n/2) + n \lg n = \Theta(n \lg^2 n)$ , which falls in the gap between cases 2 and 3 of the basic theorem.

Related material: the $n^k \lg^p n$ table. A wider version is often stated for $f(n) = \Theta(n^k \lg^p n)$ with constants $k \ge 0$ and real $p$ . It is not a CLRS theorem, but each row follows from the recursion tree (level $i$ costs $(a/b^k)^i$ times $n^k \lg^p(n/b^i)$ ):

Relation of $a$ and $b^k$	Condition on $p$	$T(n)$
$a > b^k$	any $p$	$\Theta(n^{\log_b a})$
$a = b^k$	$p > -1$	$\Theta(n^k \lg^{p+1} n)$
$a = b^k$	$p = -1$	$\Theta(n^k \lg \lg n)$
$a = b^k$	$p < -1$	$\Theta(n^k)$
$a < b^k$	any $p$	$\Theta(n^k \lg^p n)$

With $a = b^k$ every level contributes $n^k \lg^p$ of a shrinking argument, so the sum is $n^k \sum_{j=1}^{\log_b n} j^p$ up to constants: a power sum for $p > -1$ , a harmonic sum for $p = -1$ , and a convergent series for $p < -1$ . For example $2T(n/2) + n/\lg^2 n = \Theta(n)$ . Some books write $O(n^k)$ for $a < b^k$ , $p < 0$ ; that is only an upper bound, since the root alone already costs $\Theta(n^k \lg^p n)$ .

When the master theorem does not apply

Recurrence	Why not	Solution and method
$T(n) = 2T(n/2) + n \lg n$	$f$ larger than $n$ only by $\lg n$	$\Theta(n \lg^2 n)$ , extended case 2 or recursion tree
$T(n) = 2T(n/2) + n / \lg n$	$f$ smaller only by $\lg n$	$\Theta(n \lg \lg n)$ , recursion tree (harmonic sum of level costs)
$T(n) = T(n/3) + T(2n/3) + n$	unequal subproblem sizes	$\Theta(n \lg n)$ , recursion tree
$T(n) = n\,T(n/2) + 1$	$a$ is not a constant	not polynomial; unroll
$T(n) = T(n-1) + n$	subtractive, no $b > 1$	$\Theta(n^2)$ , unrolling
$T(n) = 2T(\sqrt{n}) + \lg n$	argument is not $n/b$	$\Theta(\lg n \lg \lg n)$ , change of variables
$T(n) = 0.5\,T(n/2) + n$	$a < 1$	$\Theta(n)$ by recursion tree; the theorem needs $a \ge 1$

Method 4: unrolling subtract-type recurrences

For recurrences that reduce $n$ by a constant, expand repeatedly and sum.

$T(n) = T(n-1) + c$ : $T(n) = cn + T(0) = \Theta(n)$ (linear recursion, for example recursive linear search).
$T(n) = T(n-1) + n$ : $T(n) = n + (n-1) + \dots + 1 + T(0) = n(n+1)/2 + T(0) = \Theta(n^2)$ (for example selection sort written recursively, or quicksort's worst case).
$T(n) = 2T(n-1) + 1$ , $T(1) = 1$ : $T(n) = 2^n - 1$ exactly (Tower of Hanoi moves).
$T(n) = T(n-1) + T(n-2) + 1$ , $T(0) = T(1) = 1$ : $T(n) = 2F(n+1) - 1 = \Theta(\phi^n)$ , $\phi = (1 + \sqrt{5})/2 \approx 1.618$ , where $F$ is the Fibonacci sequence (naive Fibonacci call count).
General bound: if $T(n) = a\,T(n - b) + f(n)$ with constants $a \ge 1$ , $b \ge 1$ and $f(n) = O(n^k)$ , then $T(n) = O(n^{k+1})$ when $a = 1$ and $T(n) = O(n^k a^{n/b})$ when $a > 1$ .

Change of variables

For $T(n) = 2T(\sqrt{n}) + \lg n$ , put $m = \lg n$ , so $n = 2^m$ and $\sqrt{n} = 2^{m/2}$ . Define $S(m) = T(2^m)$ . Then $S(m) = 2S(m/2) + m$ , which is case 2: $S(m) = \Theta(m \lg m)$ . Translating back, $T(n) = \Theta(\lg n \lg \lg n)$ . Similarly $T(n) = T(\sqrt{n}) + 1$ gives $S(m) = S(m/2) + 1$ , so $T(n) = \Theta(\lg \lg n)$ .

Worked examples

Recurrence	$n^{\log_b a}$	Comparison with $f$	Solution
$T(n) = 2T(n/2) + n$ (merge sort)	$n$	equal: case 2	$\Theta(n \lg n)$
$T(n) = T(n/2) + 1$ (binary search)	$n^0 = 1$	equal: case 2	$\Theta(\lg n)$
$T(n) = 8T(n/2) + n^2$ (naive block matrix multiply)	$n^3$	$f$ smaller by $n^1$ : case 1	$\Theta(n^3)$
$T(n) = 7T(n/2) + n^2$ (Strassen)	$n^{\lg 7} \approx n^{2.807}$	$f$ smaller by $n^{0.807}$ : case 1	$\Theta(n^{\lg 7})$
$T(n) = 2T(n/2) + 1$ (tree traversal)	$n$	$f$ smaller by $n^1$ : case 1	$\Theta(n)$
$T(n) = 2T(n/2) + n^2$	$n$	$f$ larger by $n^1$ ; regularity $2(n/2)^2 = n^2/2$ , $c = 1/2$ : case 3	$\Theta(n^2)$
$T(n) = 3T(n/4) + n \lg n$	$n^{0.793}$	$f$ larger by more than $n^{0.2}$ ; regularity $3(n/4)\lg(n/4) \le \tfrac{3}{4} n \lg n$ : case 3	$\Theta(n \lg n)$
$T(n) = 4T(n/2) + n^2 \lg n$	$n^2$	$f = n^2 \lg^1 n$ : extended case 2, $k = 1$	$\Theta(n^2 \lg^2 n)$
$T(n) = 9T(n/3) + n$	$n^2$	$f$ smaller by $n^1$ : case 1	$\Theta(n^2)$
$T(n) = T(2n/3) + 1$	$n^0 = 1$	equal: case 2	$\Theta(\lg n)$

Exact values check the asymptotics. With $T(1) = 1$ and $n = 2^k$ :

$T(n) = 2T(n/2) + n$ gives $T(n) = n \lg n + n$ (for $n = 1024$ : 11264).
$T(n) = 8T(n/2) + n^2$ gives $T(n) = 2n^3 - n^2$ .
$T(n) = T(n/2) + 1$ gives $T(n) = \lg n + 1$ .

Recurrence from code

Text

F(n)
    if n <= 1 then return 1
    s <- 0
    for i <- 1 to n
        for j <- 1 to n
            s <- s + 1
    return F(n/2) + F(n/2) + F(n/2) + F(n/2) + s

Four calls on $n/2$ plus $n^2$ increments: $T(n) = 4T(n/2) + n^2$ , case 2, $\Theta(n^2 \lg n)$ . Counting only the increments of s, with none for $n = 1$ , the exact total is $S(n) = n^2 \lg n$ for $n = 2^k$ (1,024 for $n = 16$ ).

Replacing the return line by return 4 * F(n/2) + s computes the same value with one call: $T(n) = T(n/2) + n^2 = \Theta(n^2)$ , and the increments total $\tfrac{4}{3}(n^2 - 1)$ (84 for $n = 8$ , 340 for $n = 16$ ). The number of recursive calls in the code, not the arithmetic in the formula, sets $a$ .

Important properties and observations

The master theorem compares $f(n)$ with $n^{\log_b a}$ polynomially; logarithmic differences fall into gaps.
The base of the logarithm in $\log_b a$ matters (it is the exponent); the base of $\lg n$ in the case 2 answer does not.
The theorem gives $\Theta$ , so it gives both an upper and a lower bound. If $f$ is given only as $O(\cdot)$ , a matching toll-driven lower bound may be unavailable. However, case 1 still gives $\Theta(n^{\log_b a})$ for a nonnegative toll and a positive constant base cost, because the leaves supply that lower bound.
Adding a constant to an argument requires a terminating cutoff: for $T(n)=2T(n/2+17)+n$ , choose a constant base-case cutoff $n_0>34$ , with rounding handled so recursive arguments shrink above it. Then the solution is $\Theta(n\lg n)$ . For example, floor rounding with integer $n_0\ge35$ works. An arbitrary unchanged small base case may not terminate: 34 maps to itself. $T(n) = 2T(n/2 + 17) + n$ is still $\Theta(n \lg n)$ .
In a substitution proof, never absorb the error term with $O(\cdot)$ inside the induction; carry the explicit constant.

GATE examination perspective

Direct application. identify $a$ , $b$ , $f$ , compute $\log_b a$ , decide the case, and check regularity for case 3 when $f$ is not a polynomial.
Recurrence from code. write the recurrence first (how many recursive calls, of what size, plus the non-recursive work), then solve it. A function that calls itself twice on $n - 1$ is exponential, not quadratic.
Traps. F(n/2) + F(n/2) is two calls but 2 * F(n/2) is one; $2T(n/2) + n \lg n$ is not $\Theta(n \lg n)$ ; $2T(n/2) + n/\lg n$ is $\Theta(n \lg \lg n)$ , not $\Theta(n)$ ; $T(n-1) + n$ is not covered by the master theorem; unequal splits need a recursion tree; $T(\sqrt{n})$ needs a change of variables.
Exact answers. when asked for a value (for example, the number of moves or calls), solve the recurrence exactly, not asymptotically.

Summary

Four methods: substitution (guess and induct), recursion tree (sum level costs), master theorem (compare $f$ with $n^{\log_b a}$ ), unrolling (subtract-type).
Master theorem (CLRS 3e, Section 4.5), $a \ge 1$ , $b > 1$ : case 1 leaves dominate, $\Theta(n^{\log_b a})$ ; case 2 balanced, $\Theta(n^{\log_b a} \lg n)$ ; case 3 root dominates, $\Theta(f(n))$ , only with the regularity condition.
Extended case 2 (fixed $k\ge0$ ): $f = \Theta(n^{\log_b a} \lg^k n)$ gives $\Theta(n^{\log_b a} \lg^{k+1} n)$ .
Not covered: unequal splits, non-constant $a$ , subtractive recurrences, non-polynomial gaps such as $n/\lg n$ .
Change of variables $m = \lg n$ handles $T(\sqrt{n})$ .

Sources

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, Chapter 4, Sections 4.3 (substitution method), 4.4 (recursion-tree method), 4.5 (the master method and the master theorem) and 4.6 (proof of the master theorem; Exercise 4.6-2, the extended case 2).