Solving recurrences: substitution, tree and Master theorem

Why it exists

A recursive algorithm's cost satisfies an equation in terms of itself: mergesort on $n$ items sorts two halves and then merges, so $T(n) = 2T(n/2) + \Theta(n)$. To compare algorithms we need $T(n)$ in closed form, at least its order. Three tools do almost everything: the recursion tree (see the pattern), the Master theorem (a shortcut for the most common shape), and substitution (proof by induction of a guess).

Prerequisites

You need asymptotic notation (asymptotic notation) and a little about recurrence relations (recurrence relations).

Precise definitions

Recurrence. An equation defining $T(n)$ by smaller values of $T$ together with a base case (usually $T(1) = \Theta(1)$, which we assume whenever it is not written). Floors and ceilings in the arguments (n/2 as $\lfloor n/2 \rfloor$) do not change the order for the recurrences here, so one pretends that $n$ is a power of the divisor.

Divide-and-conquer recurrence. $T(n) = a\,T(n/b) + f(n)$ with $a \ge 1$ subproblems of size $n/b$ ($b > 1$) and $f(n)$ the cost of dividing and combining.

Recursion tree method. Draw the tree of calls. Level $i$ has $a^i$ subproblems of size $n/b^i$; if $f(n) = n^k$, one subproblem at level $i$ costs $(n/b^i)^k$ and the whole level costs $a^i (n/b^i)^k = n^k (a / b^k)^i$. There are $\log_b n + 1$ levels, the last one with $a^{\log_b n} = n^{\log_b a}$ leaves. The total is the sum over the levels, a geometric series with ratio $a/b^k$:

• ratio $> 1$ (the levels get more expensive downwards): dominated by the leaves, $\Theta(n^{\log_b a})$;
• ratio $= 1$ (every level costs the same, $n^k$): $\Theta(n^k \log n)$;
• ratio $< 1$ (the levels get cheaper): dominated by the root, $\Theta(n^k) = \Theta(f(n))$.

The Master theorem. Let $T(n) = a\,T(n/b) + f(n)$ with constants $a \ge 1$, $b > 1$, and let $c = \log_b a$ (so $n^c$ is the number of leaves). Then

1. If $f(n) = O(n^{c - \varepsilon})$ for some $\varepsilon > 0$ ($f$ polynomially smaller): $T(n) = \Theta(n^{c})$.
2. If $f(n) = \Theta(n^{c} \log^{p} n)$ with $p \ge 0$ ($f$ the same order, up to logarithms): $T(n) = \Theta(n^{c} \log^{p+1} n)$. For $p = 0$: $\Theta(n^c \log n)$.
3. If $f(n) = \Omega(n^{c + \varepsilon})$ for some $\varepsilon > 0$ ($f$ polynomially larger) and the regularity condition $a f(n/b) \le \delta f(n)$ holds for some constant $\delta < 1$ and large $n$: $T(n) = \Theta(f(n))$.

For $f(n) = n^k \log^p n$ the conditions reduce to comparing $k$ with $c = \log_b a$: $k < c$ is case 1; $k = c$ is case 2; $k > c$ is case 3 (the regularity condition holds automatically for such $f$). The theorem does not cover the gap where $f$ is smaller than $n^c$ only by a logarithmic factor: for $f(n) = n^c / \log n$ the solution is $\Theta(n^c \log \log n)$, and for $f(n) = n^c \log^{p} n$ with $p < -1$ it is $\Theta(n^c)$ (these need the tree).

Substitution method. (1) Guess the form of the solution (from the tree, or from small cases). (2) Prove by induction that $T(n) \le c\, g(n)$ for a suitable constant $c$, assuming it for smaller arguments, substituting into the recurrence. (3) Check the base case. If the induction fails by a lower-order term, strengthen the hypothesis by subtracting a lower-order term.

Change of variable. For $T(n) = T(\sqrt n) + 1$ put $n = 2^m$: $S(m) = T(2^m)$ satisfies $S(m) = S(m/2) + 1$, so $S(m) = \Theta(\log m)$ and $T(n) = \Theta(\log \log n)$.

Recurrences with subtraction. $T(n) = T(n-1) + f(n)$ is solved by summing: $T(n) = T(0) + \sum_{i=1}^{n} f(i)$ (so $f = n$ gives $n(n+1)/2$, $f = 1$ gives $n$). With a multiplier, $T(n) = 2T(n-1) + 1$ doubles at each step: $T(n) = 2^n - 1$, exponential. $T(n) = T(n-1) + T(n-2)$ grows like the Fibonacci numbers, $\Theta(\varphi^n)$ with $\varphi = (1 + \sqrt 5)/2 \approx 1.618$. The Master theorem does not apply to any of these (the subproblem size is $n - 1$, not $n/b$).

How it works

The recursion tree of $T(n) = 2T(n/2) + n$ for $n = 1024$. Every level costs 1024: two subproblems of half the size replace one, and the sum of sizes is constant. There are 11 levels, so the total is about $n \log_2 n$. This is the pattern of mergesort.

For $T(n) = T(n/2) + n$ the levels cost $1024, 512, 256, \ldots$: a geometric series with ratio $1/2$, dominated by the root. The total is about $2n$: $T(n) = \Theta(n)$ (case 3).

For $T(n) = 4T(n/2) + n$ the levels cost $n, 2n, 4n, \ldots$: ratio 2, dominated by the leaves, $n^{\log_2 4} = n^2$ of them: $T(n) = \Theta(n^2)$ (case 1).

Ten Master theorem verdicts for standard algorithms. For each, $T(b^m)$ was evaluated exactly for $m$ up to 60 and the claimed bound was confirmed (the ratio $T(n)/g(n)$ stays steady, so it is neither too low nor too high by a factor such as $\log n$).

And the recurrences that need other tools:

Worked examples

Cheat box

Traps and GATE patterns

Connections

Recurrences describe the cost of divide and conquer algorithms (mergesort, quicksort, binary search) and, with sums, of recursive algorithms generally. The tools of asymptotic notation are used throughout; analysing loops covers the iterative case. The mathematical side of linear recurrences is in recurrence relations.

PYQs

Consider the following recurrence relations:
For all n>1,
T1(n)=4T1(n/2)+T2(n)
T2(n)=5T2(n/4)+Θ(log2n)
Assume that for all n≤1, T1(n)=1 and T2(n)=1.
Which one of the following options is correct?

Which of the following can be recurrence
relation(s) corresponding to an algorithm with time
complexity O(n)?

Consider the following recurrence relation:
T(n)=2T(n-1)+ n2n for n>0, T(0)=1
Which ONE of the following options is CORRECT?

Consider the following recurrence relation:

T(n) = {√n ⋅ T(√n) + n
for n ≥ 1
1
for n = 1
Which one of the following options is CORRECT?

Let T(n) be the recurrence relation defined as
follows:
T(0) = 1,
T(1) = 2 and
T(n) = 5T(n - 1) - 6T(n - 2) for n ≥ 2
Which one of the following statement is TRUE?

For constants a ≥ 1 and b > 1, consider the
following recurrence defined on the non-negative
integers:
T(n) = a T (n/b) + f(n)
Which one of the following options is correct about
the recurrence T(n) ?

Consider the following recurrence relation.
T(n) = T(n/2) + T(2n/5) + 7n
, if n > 0
{
1 , if n = 0

For parameters a and b, both of which are ω(1),
T(n) = T(n 1/a ) + 1, and T(b)=1. Then T(n) is:

Consider the recurrence function
2 × T(√n) + 1,
if n > 2

The given diagram shows the flowchart for a
recursive function A(n). Assume that all
statements, except for the recursive calls, have
O(1) time complexity. If the worst-case time
complexity of this function is O(nα ), then the least
possible value (accurate up to two decimal
positions) of α is
.
Flowchart for Recursive Function A(n)

Which one of the following correctly
determines the solution of the recurrence relation
with T(1)=1?
T(n)=2T(n/2) + logn

The running time of an algorithm is represented
by the following recurrence relation:
n ; n ≤ 3
T(n) = {
n
T ( ) + cn; otherwise
3

When n = 2(2k) for some k >= 0, the recurrence
relation T(n) = √(2)T(n/2) + √(n), T(1) = 1
evaluates to :

What is the Asymptotic Notation of the following
recursive function:
int DoSomething (int n) {
if (n <= 2)
return 1;
else
return (DoSomething (floor(sqrt(n))) + n); }

Consider the following recurrence:

T(n) = 2T([√n]) + 1, T(1) = 1
Which one of the following is true?
int i,n;
for(i=2;i<=sqrt(n);i++)
if(n%i == 0)
{printf("Not Primen"); return 0;}
return 1;
} Let T(n)denote the number of times the for
loop is executed by the program on input n.
Which of the following is TRUE?

Suppose T(n)=2T(n/2)+n,
T(0)=T(1)=1
Which one of the following is FALSE?

Consider the following C-function:
double foo (int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n; i++)
sum += foo (i);
return sum;
}
}
Suppose we modify the above function foo() and
store the values of foo (i), 0⁡≤⁡i < n, as and
when they are computed. With this modification,
the time complexity for function foo() is
significantly reduced. The space complexity of
the modified function would be:

Consider the following C functions:

int f1(int n)

{

if (n == 0 || n == 1)

return n;

else

return (2 * f1(n - 1) + 3 * f1(n - 2));

}

int f2(int n)

{

int i;

int X[N], Y[N], Z[N];

X[0] = Y[0] = Z[0] = 0;

X[1] = 1;

Y[1] = 2;

Z[1] = 3;

for (i = 2; i <= n; i++) {
        X[i] = Y[i - 1] + Z[i - 2];
        Y[i] = 2 * X[i];
        Z[i] = 3 * X[i];

}

return X[n];

}

The running time of f1(n) and f2(n) are

f1(8) and f2(8) return the values

The recurrence relation capturing the optimal
execution time of the Towers of Hanoi problem with
n discs is

Self-check

Revision card

References