Recurrences

Part 5 · Recursion · Chapter 15 · Lecture notes, volume 5 (PDF) · Exercises: Recurrences

Introduction

In the chapter Recursion we counted the steps of a recursive algorithm line by line, and we noticed that the number of steps executed by a call depends on the number of steps executed by its recursive calls, which are calls of the same algorithm on a smaller input. The quantity we want to compute is therefore defined in terms of itself: this is a recurrence.

In this chapter we first define recurrences and show where they come from (Section 15.1). Then we study three methods to solve them, that is, to obtain their closed form or at least their order of growth:

• the expansion method (Section 15.2), which unrolls the recurrence until the boundary condition is reached;

• the substitution method (Section 15.3), which proves a guessed bound by induction;

• the recursion-tree method (Section 15.4), which visualises the costs of all the calls and sums them level by level.

Finally (Section 15.5) we draw the recursion tree of a generic divide-and-conquer recurrence: the three behaviours that we observe there are the starting point of the chapter The Master Theorem.

15.1 Recurrences

Definition 15.1: recurrence

A recurrence is an equation (or an inequality) that describes a function \(T:\N\to\R\) in terms of its values on smaller inputs.

• Each recurrence has boundary conditions, which give the value of the function when the input size is small, that is, when \(n\) reaches (or is below) a specific value \(n_0\). Precisely, the boundary conditions are

  \[ T(n)=g(n) \qquad \text{if } n\le n_0, \]

  where \(g(n)\) is the value of the function for the small values of \(n\). Typically \(n_0=1\) and the boundary condition is \(T(1)=\Theta(1)\).

• Solving a recurrence means determining a closed form of \(T(n)\) or, at least, its order of growth, that is, a function \(h(n)\) such that \(T(n)=\Theta(h(n))\) (or \(T(n)=O(h(n))\), or \(T(n)=\Omega(h(n))\)).

Example 15.1: A first recurrence

Consider the recurrence

\[ T(n)= \begin{cases} 1 & \text{if } n=1\\ T(n-1)+n & \text{if } n>1 \end{cases} \]

The boundary condition is \(T(1)=1\) (here \(n_0=1\)); for \(n>1\) every value is obtained from the previous one:

• \(T(1)=1\) (boundary condition);

• \(T(2)=T(1)+2=1+2=3\);

• \(T(3)=T(2)+3=3+3=6\);

• \(T(4)=T(3)+4=6+4=10\).

The recurrence defines \(T(n)\) for every \(n\in\N\), \(n\ge 1\), but computing \(T(n)\) in this way requires \(n-1\) additions. In Example 15.4 we solve it and obtain the closed form \(T(n)=\frac{n(n+1)}{2}\).

15.1.1 Recurrences and recursive algorithms

Recurrences are the natural tool to determine the asymptotic complexity of recursive algorithms.

In this chapter recurrences are mathematical objects, and we use a generic function \(T(n)\). When we analyse a recursive algorithm, the function described by the recurrence is the number of steps \(S(n)\) executed in the worst case on an input of size parameter \(n\) (see the chapter Recursion): the number of steps of a call is the number of steps executed by the call itself plus the number of steps executed by its recursive calls.

• Consider the following recursive algorithm that computes the sum of the entries of an array.

Algorithm: RecursiveSum

Input: An array \(a[1..n]\) of \(n\ge 1\) integer numbers

Output: The sum \(a[1]+a[2]+\cdots+a[n]\)

1function RecursiveSum(a, n)

2if \(n = 1\) then

3return \(a[1]\)

4end

5\(s :=\) RecursiveSum(\(a, n-1\))

6return \(s + a[n]\)

7end

Run in Colab:PythonC++Java

Example 15.2: The recurrence of RecursiveSum

Let \(S(n)\) be the number of steps executed by RecursiveSum on an array of size \(n\). We count the executions of each line.

• If \(n=1\), lines 2 and 3 are executed once: \(S(1)=2\).

• If \(n>1\), lines 2, 5 and 6 are executed once (\(3\) steps), and in addition the recursive call at line 5 executes \(S(n-1)\) steps.

Therefore

\[ S(n)= \begin{cases} 2 & \text{if } n=1\\ S(n-1)+3 & \text{if } n>1 \end{cases} \]

For instance, \(S(2)=2+3=5\), \(S(3)=5+3=8\) and \(S(4)=8+3=11\). In Example 15.3 we show that \(S(n)=3n-1=\Theta(n)\).

15.1.2 Different forms of recurrences

The shape of the recurrence mirrors the way the algorithm splits its input. The most common shapes are the following.

• Divide-and-conquer. A recursive algorithm divides the problem into \(a\) subproblems, each of size \(n/b\), solves them recursively and combines their solutions. This gives rise to a recurrence of the form

  \[ T(n)=a\,T\left(\frac{n}{b}\right)+f(n). \]

  For example, the algorithm MergeSort (studied in the chapter Recursive algorithms) gives rise to

  \[ T(n)=2T(n/2)+\Theta(n). \]

• Unequal split. A recursive algorithm might divide the problem into subproblems of different sizes. For example, if the input is divided into a \(1/3\) and a \(2/3\) split, we obtain the recurrence

  \[ T(n)=T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+f(n), \]

  where \(f(n)\) is the time required to divide the problem and to combine the solutions of the subproblems.

• Decrease-and-conquer. Subproblems are not necessarily a constant fraction of the original problem. For example, a recursive algorithm might create just one subproblem containing one element less than the original problem (as RecursiveSum). This gives rise to the recurrence

  \[ T(n)=T(n-1)+f(n). \]

• Several subproblems of size \(n-1\). For example, the algorithm that solves the Tower of Hanoi puzzle with \(n\) disks moves \(n-1\) disks, then one disk, then again \(n-1\) disks, giving rise to the recurrence

  \[ T(n)=2\,T(n-1)+1, \]

  whose solution is exponential in \(n\) (see Example 15.5).

Definition 15.2: recurrence in standard form

A recurrence is in standard form if it can be written as

\[\begin{equation*} T(n)=a\,T\left(\frac{n}{b}\right)+f(n) \label{eq:rec:standardForm} \tag{15.1} \end{equation*}\]

where

• \(n\) is the size of the input (typically \(n\in\N\));

• \(a\ge 1\) is the number of subproblems to solve;

• \(\frac{n}{b}\) is the size of each subproblem (\(b>1\));

• \(f(n)\) is the time required to divide the problem and to combine the solutions of the subproblems.

• Including the boundary conditions, a recurrence in standard form is

  \[ T(n)= \begin{cases} g(1) & \text{if } n=1\\ a\,T\left(\frac{n}{b}\right)+f(n) & \text{if } n>1 \end{cases} \]

  where \(g(1)\) is the time required to solve a subproblem of size \(1\), typically \(g(1)=\Theta(1)\).

• Occasionally, we shall see recurrences that are not equalities but inequalities, such as

  \[ T(n)\le a\,T\left(\frac{n}{b}\right)+f(n). \]

  Because such a recurrence states only an upper bound on \(T(n)\), its solution is given in \(O\)-notation rather than in \(\Theta\)-notation.

• Similarly, if the inequality is reversed,

  \[ T(n)\ge a\,T\left(\frac{n}{b}\right)+f(n), \]

  the recurrence gives only a lower bound on \(T(n)\), and its solution is given in \(\Omega\)-notation.

15.1.3 Methods for solving recurrences

• In this chapter we study three methods for solving recurrences:

  1. The expansion method (also called iteration or unrolling): we repeatedly substitute the recurrence into itself until we reach the boundary condition, and we compute the resulting summation.

  2. The substitution method: we guess a bound and then use mathematical induction to prove that the guess is correct.

  3. The recursion-tree method: we convert the recurrence into a tree whose nodes represent the costs incurred at the various levels of the recursion, and we bound the resulting summations.

• In the chapter The Master Theorem we study a fourth method, the Master Theorem, which provides directly the solution of recurrences in standard form \(\eqref{eq:rec:standardForm}\).

Before applying the methods, we fix two technical points: which details of a recurrence can be neglected, and which summations appear most often.

15.1.4 Technicalities in recurrences

• We often neglect certain technical details when we state and solve recurrences.

• Floors and ceilings. Consider the recurrence

  \[ T(n)= \begin{cases} \Theta(1) & \text{if } n=1\\ 2\,T\left(\frac{n}{2}\right)+\Theta(n) & \text{if } n>1 \end{cases} \]

  When \(n\) is odd, the two subproblems cannot both have size \(n/2\) (which is not an integer): typically, they have sizes \(\lceil n/2\rceil\) and \(\lfloor n/2\rfloor\). The precise recurrence is therefore

  \[ T(n)= \begin{cases} \Theta(1) & \text{if } n=1\\ T\left(\lceil n/2\rceil\right)+T\left(\lfloor n/2\rfloor\right)+\Theta(n) & \text{if } n>1 \end{cases} \]

  The two recurrences have the same asymptotic solution. Since we are interested in the order of growth, floors and ceilings can usually be omitted.

• Exact powers. For the same reason, when solving a recurrence in standard form \(\eqref{eq:rec:standardForm}\) we often assume that \(n\) is an exact power of \(b\), that is, \(n=b^k\) for some \(k\in\N\). In this way all the subproblem sizes \(n/b, n/b^2,\dots,1\) are integers. In the example above, we assume \(n=2^k\).

• Boundary conditions. Boundary conditions are another class of details that we typically ignore. Since the running time of an algorithm on an input of constant size is a constant, the recurrences that arise from the analysis of algorithms generally satisfy

  \[ T(n)=\Theta(1) \qquad \text{for sufficiently small } n. \]

  Consequently, for convenience, we shall generally omit the boundary conditions and assume that \(T(n)\) is constant for small \(n\). Changing the value of \(T(1)\) typically changes the exact solution, but not its order of growth.

Omitting floors, ceilings and boundary conditions, and assuming that \(n\) is an exact power of \(b\), simplifies the computations. When a rigorous proof is required (for example in the substitution method), these details must be handled explicitly.

15.1.5 Useful summations

All three methods end with a summation: the costs of the single calls must be added up. The following formulas are used throughout the chapter.

Observation 15.3: useful summations and logarithms

• The arithmetic series: for every \(n\ge 1\)

  \[\begin{equation*} \sum_{i=1}^{n} i = 1+2+\cdots+n=\frac{n(n+1)}{2}. \label{eq:rec:arith} \tag{15.2} \end{equation*}\]

• The geometric series: for every real number \(x\neq 1\) and every \(k\in\N\)

  \[\begin{equation*} \sum_{i=0}^{k} x^i = 1+x+x^2+\cdots+x^k=\frac{x^{k+1}-1}{x-1}. \label{eq:rec:geomFinite} \tag{15.3} \end{equation*}\]

  In particular, for \(x=2\),

  \[\begin{equation*} \sum_{i=0}^{k-1} 2^i = 2^k-1. \label{eq:rec:geomTwo} \tag{15.4} \end{equation*}\]

• The infinite decreasing geometric series: for every real number \(x\) with \(|x|<1\)

  \[\begin{equation*} \sum_{i=0}^{\infty} x^i = \frac{1}{1-x}. \label{eq:rec:geomInfinite} \tag{15.5} \end{equation*}\]

• Two properties of logarithms: for every \(a,b,n>0\) (with \(b\neq 1\))

  \[\begin{equation*} a^{\log_b n}=n^{\log_b a}, \qquad \log_b n=\frac{\log_2 n}{\log_2 b}. \label{eq:rec:logProps} \tag{15.6} \end{equation*}\]

Proof

Arithmetic series. Writing the sum twice, once in increasing and once in decreasing order, and adding term by term, we obtain \(n\) pairs, each with sum \(n+1\): twice the sum is \(n(n+1)\).

Geometric series. Multiplying the sum by \(x-1\), all the intermediate terms cancel:

\[ (x-1)\sum_{i=0}^{k}x^i=\sum_{i=1}^{k+1}x^i-\sum_{i=0}^{k}x^i=x^{k+1}-1 , \]

and we divide by \(x-1\neq 0\). For \(x=2\) and \(k-1\) in place of \(k\) we obtain \(2^k-1\).

Infinite series. If \(|x|<1\), then \(x^{k+1}\to 0\) for \(k\to\infty\), and the finite sum tends to \(\frac{0-1}{x-1}=\frac{1}{1-x}\).

Logarithms. \(a^{\log_b n}=\big(b^{\log_b a}\big)^{\log_b n}=\big(b^{\log_b n}\big)^{\log_b a}=n^{\log_b a}\). Moreover \(n=b^{\log_b n}\) gives \(\log_2 n=\log_b n\cdot\log_2 b\). □

• Since all the terms are positive when \(0<x<1\), every finite sum \(\sum_{i=0}^{k} x^i\) is smaller than \(\frac{1}{1-x}\): the infinite series gives an upper bound on a finite geometric sum that does not depend on \(k\).

• The second property of the logarithms shows that logarithms in different bases differ by a constant factor; hence, inside \(\Theta\), \(O\) and \(\Omega\) the base of the logarithm is irrelevant.

15.2 The expansion method

The most direct way to solve a recurrence is to apply it again and again: each application replaces a value of \(T\) with a value on a smaller argument, and after enough applications only the boundary condition remains.

In the expansion method (also called iteration or unrolling) we:

1. substitute the recurrence into itself a few times, until we recognise the general pattern after \(k\) substitutions;

2. choose \(k\) such that the argument reaches the boundary condition;

3. compute (or bound) the resulting summation.

• The method gives an exact closed form when the summation can be computed. The pattern recognised in step 1 can be proved rigorously by induction on \(k\).

We start with the recurrences of the decrease-and-conquer type, \(T(n-1)+f(n)\), and then move to the divide-and-conquer type, \(a\,T(n/2)+f(n)\).

Example 15.3: \(T(n)=T(n-1)+c\)

Let \(c,d>0\) be constants and

\[ T(n)= \begin{cases} d & \text{if } n=1\\ T(n-1)+c & \text{if } n>1 \end{cases} \]

• Step 1 (expand).

  \[\begin{align*} T(n) &= T(n-1)+c\\ &= \big(T(n-2)+c\big)+c = T(n-2)+2c\\ &= \big(T(n-3)+c\big)+2c = T(n-3)+3c\\ &\;\;\vdots\\ &= T(n-k)+k\,c. \end{align*}\]

• Step 2 (boundary condition). The boundary condition is reached when \(n-k=1\), that is, \(k=n-1\).

• Step 3 (sum).

  \[ T(n)=T(1)+(n-1)\,c=c\,n+(d-c)=\Theta(n). \]

For RecursiveSum (Example 15.2) we have \(c=3\) and \(d=2\), hence

\[ S(n)=3(n-1)+2=3n-1=\Theta(n), \]

which gives \(S(2)=5\), \(S(3)=8\), \(S(4)=11\), as computed directly from the recurrence.

Example 15.4: \(T(n)=T(n-1)+n\)

Let

\[ T(n)= \begin{cases} 1 & \text{if } n=1\\ T(n-1)+n & \text{if } n>1 \end{cases} \]

• Step 1 (expand).

  \[\begin{align*} T(n) &= T(n-1)+n\\ &= T(n-2)+(n-1)+n\\ &= T(n-3)+(n-2)+(n-1)+n\\ &\;\;\vdots\\ &= T(n-k)+(n-k+1)+\cdots+(n-1)+n. \end{align*}\]

• Step 2 (boundary condition). \(n-k=1\), that is, \(k=n-1\).

• Step 3 (sum). Using the arithmetic series \(\eqref{eq:rec:arith}\),

  \[ T(n)=T(1)+2+3+\cdots+n=1+2+\cdots+n=\frac{n(n+1)}{2}=\Theta(n^2). \]

  Indeed,

  \[ \lim_{n\to\infty}\frac{n(n+1)/2}{n^2}=\lim_{n\to\infty}\frac{1}{2}\left(1+\frac{1}{n}\right)=\frac{1}{2}\in\R_{>0}. \]

The closed form gives \(T(1)=1\), \(T(2)=3\), \(T(3)=6\), \(T(4)=10\), the values of Example 15.1.

Example 15.5: \(T(n)=2T(n-1)+1\): the Tower of Hanoi

Let

\[ T(n)= \begin{cases} 1 & \text{if } n=1\\ 2\,T(n-1)+1 & \text{if } n>1 \end{cases} \]

• Step 1 (expand).

  \[\begin{align*} T(n) &= 2\,T(n-1)+1\\ &= 2\big(2\,T(n-2)+1\big)+1 = 2^2\,T(n-2)+2+1\\ &= 2^2\big(2\,T(n-3)+1\big)+2+1 = 2^3\,T(n-3)+2^2+2+1\\ &\;\;\vdots\\ &= 2^k\,T(n-k)+\sum_{i=0}^{k-1}2^i. \end{align*}\]

• Step 2 (boundary condition). \(n-k=1\), that is, \(k=n-1\).

• Step 3 (sum). Using \(\eqref{eq:rec:geomTwo}\),

  \[ T(n)=2^{n-1}\,T(1)+\left(2^{n-1}-1\right)=2^{n-1}+2^{n-1}-1=2^n-1=\Theta(2^n). \]

This is the number of moves needed to solve the Tower of Hanoi puzzle with \(n\) disks: the running time is exponential in \(n\). The function hanoi of the code of the course counts its moves; running it we obtain

\(n\)	1	2	3	4	5	6	7	8	10
moves	1	3	7	15	31	63	127	255	1023

that is, exactly \(2^n-1\) moves.

The next two recurrences halve the size of the problem at each call. To avoid floors we assume that \(n\) is an exact power of \(2\).

Example 15.6: \(T(n)=T(n/2)+c\)

Let \(c,d>0\) be constants, let \(n=2^k\) be an exact power of \(2\), and

\[ T(n)= \begin{cases} d & \text{if } n=1\\ T\left(\frac{n}{2}\right)+c & \text{if } n>1 \end{cases} \]

• Step 1 (expand).

  \[ T(n) = T\left(\frac{n}{2}\right)+c = T\left(\frac{n}{2^2}\right)+2c = T\left(\frac{n}{2^3}\right)+3c = \cdots = T\left(\frac{n}{2^j}\right)+j\,c. \]

• Step 2 (boundary condition). \(\frac{n}{2^j}=1\), that is, \(j=\log_2 n\).

• Step 3 (sum).

  \[ T(n)=T(1)+c\log_2 n=c\log_2 n+d=\Theta(\log_2 n). \]

This recurrence describes, for instance, the recursive version of BinarySearch: at each call the size of the sub-array is halved.

Example 15.7: \(T(n)=2T(n/2)+n\)

Let \(n=2^k\) be an exact power of \(2\) and

\[ T(n)= \begin{cases} 1 & \text{if } n=1\\ 2\,T\left(\frac{n}{2}\right)+n & \text{if } n>1 \end{cases} \]

• Step 1 (expand).

  \[\begin{align*} T(n) &= 2\,T\left(\frac{n}{2}\right)+n\\ &= 2\left(2\,T\left(\frac{n}{2^2}\right)+\frac{n}{2}\right)+n = 2^2\,T\left(\frac{n}{2^2}\right)+2n\\ &= 2^2\left(2\,T\left(\frac{n}{2^3}\right)+\frac{n}{2^2}\right)+2n = 2^3\,T\left(\frac{n}{2^3}\right)+3n\\ &\;\;\vdots\\ &= 2^j\,T\left(\frac{n}{2^j}\right)+j\,n. \end{align*}\]

• Step 2 (boundary condition). \(j=\log_2 n\), so that \(2^j=n\).

• Step 3 (sum).

  \[ T(n)=n\,T(1)+n\log_2 n=n\log_2 n+n=\Theta(n\log_2 n). \]

Check: from the recurrence \(T(2)=2+2=4\), \(T(4)=8+4=12\), \(T(8)=24+8=32\), and from the closed form \(T(8)=8\cdot 3+8=32\).

The expansion method works well when the recurrence has a single recursive term. With several recursive terms of different sizes (for example \(T(n/3)+T(2n/3)\)) the expansion quickly becomes unmanageable: in these cases the recursion-tree method (Section 15.4) is more convenient.

15.3 The substitution method

The expansion method needs exact subproblem sizes: with floors and ceilings the pattern is no longer clean. When we already have a good idea of the solution, a more robust approach is to prove it by induction.

The substitution method comprises two steps:

1. guess the form of the solution (for example \(T(n)\le c\,n\log_2 n\), with \(c\) an unknown constant);

2. use mathematical induction to find the constants and show that the solution works.

• The name comes from the fact that, in the inductive step, we substitute the guessed bound for the values of the function on the smaller inputs.

• The method is very powerful, but it requires a good guess. The guess can come from experience (similar recurrences), from the expansion method or from a recursion tree.

• We can use the substitution method to prove upper bounds (\(O\)) and lower bounds (\(\Omega\)) separately. Both together give \(\Theta\).

• Since the asymptotic notation requires the bound only for \(n\ge n_0\), we are free to choose \(n_0\): this is useful when the bound does not hold for the smallest values of \(n\).

15.3.1 An example with floors: upper bound

• Consider the recurrence

  \[\begin{equation*} T(n)= \begin{cases} 1 & \text{if } n=1\\ 2\,T\left(\lfloor n/2\rfloor\right)+n & \text{if } n>1 \end{cases} \label{eq:rec:subsMain} \tag{15.7} \end{equation*}\]

• From Example 15.7 (where \(n\) is a power of \(2\)) we guess \(T(n)=O(n\log_2 n)\). We want to prove that there exist constants \(c>0\) and \(n_0\) such that

  \[ T(n)\le c\,n\log_2 n \qquad \text{for all } n\ge n_0. \]

Inductive step. Assume that the bound holds for all the values \(m\) with \(n_0\le m<n\), in particular for \(m=\lfloor n/2\rfloor\) (this requires \(\lfloor n/2\rfloor\ge n_0\)):

\[ T\left(\lfloor n/2\rfloor\right)\le c\,\lfloor n/2\rfloor\log_2\lfloor n/2\rfloor. \]

Substituting into the recurrence:

\[\begin{align*} T(n) &\le 2\,c\,\lfloor n/2\rfloor\log_2\lfloor n/2\rfloor+n\\ &\le 2\,c\,\frac{n}{2}\log_2\frac{n}{2}+n && \text{(since } \lfloor n/2\rfloor\le n/2\text{)}\\ &= c\,n\log_2 n-c\,n\log_2 2+n\\ &= c\,n\log_2 n-c\,n+n\\ &\le c\,n\log_2 n, \end{align*}\]

where the last step holds as long as \(c\ge 1\).

Base cases. The induction needs the bound to hold for the boundary conditions. However, for \(n=1\):

\[ T(1)=1 > c\cdot 1\cdot\log_2 1=0, \]

for every \(c\). So the bound does not hold for \(n=1\). We take advantage of the freedom of choosing \(n_0\): we prove the bound for \(n\ge n_0=2\).

• For \(n\ge 4\) we have \(\lfloor n/2\rfloor\ge 2\), so the inductive step only uses values of \(T\) on arguments \(\ge 2\).

• For \(n=2\) and \(n=3\) we have \(\lfloor n/2\rfloor=1\), so the inductive step would use \(T(1)\), which does not satisfy the bound. Therefore \(n=2\) and \(n=3\) must be treated as base cases.

From the recurrence, \(T(2)=2\,T(1)+2=4\) and \(T(3)=2\,T(1)+3=5\). We need

\[ 4\le c\cdot 2\log_2 2=2c \qquad\text{and}\qquad 5\le c\cdot 3\log_2 3. \]

Both hold for \(c\ge 2\) (since \(3\log_2 3\approx 4.75\), we have \(2\cdot 3\log_2 3\approx 9.51\ge 5\)).

Observation 15.4: upper bound for \(2T(\lfloor n/2\rfloor)+n\)

The function \(T(n)\) defined in \(\eqref{eq:rec:subsMain}\) satisfies \(T(n)\le 2\,n\log_2 n\) for all \(n\ge 2\). Hence \(T(n)=O(n\log_2 n)\).

Proof

Let \(c=2\). We proceed by strong induction on \(n\ge 2\).

Base cases \(n=2,3\): \(T(2)=4\le 2\cdot 2\cdot\log_2 2=4\) and \(T(3)=5\le 2\cdot 3\log_2 3\approx 9.51\).

Inductive step \(n\ge 4\): we have \(2\le\lfloor n/2\rfloor<n\), so by the inductive hypothesis \(T(\lfloor n/2\rfloor)\le 2\lfloor n/2\rfloor\log_2\lfloor n/2\rfloor\). Then

\[ T(n)\le 4\lfloor n/2\rfloor\log_2\lfloor n/2\rfloor+n\le 2n\log_2\frac{n}{2}+n=2n\log_2 n-2n+n\le 2n\log_2 n. \qedhere \]

□

15.3.2 An example with floors: lower bound

• We now prove \(T(n)=\Omega(n\log_2 n)\) for the same recurrence \(\eqref{eq:rec:subsMain}\). We look for a constant \(d>0\) such that \(T(n)\ge d\,n\log_2 n\) for all \(n\ge 1\).

• For the lower bound, the floor works against us: we need lower bounds on \(\lfloor n/2\rfloor\). For every \(n\ge 2\):

  \[ 2\lfloor n/2\rfloor\ge n-1 \qquad\text{and}\qquad \lfloor n/2\rfloor\ge \frac{n}{3}. \]

  The first holds because \(\lfloor n/2\rfloor\ge (n-1)/2\). The second holds for \(n=2\) (\(1\ge 2/3\)) and, for \(n\ge 3\), because \((n-1)/2\ge n/3\) is equivalent to \(n\ge 3\).

Inductive step (\(n\ge 2\)). Assume \(T(\lfloor n/2\rfloor)\ge d\lfloor n/2\rfloor\log_2\lfloor n/2\rfloor\). Since \(\lfloor n/2\rfloor\ge 1\), the factor \(\log_2\lfloor n/2\rfloor\) is non-negative, and

\[\begin{align*} T(n) &\ge 2\,d\,\lfloor n/2\rfloor\log_2\lfloor n/2\rfloor+n\\ &\ge d\,(n-1)\log_2\frac{n}{3}+n\\ &= d\,n\log_2 n-d\,n\log_2 3-d\log_2 n+d\log_2 3+n\\ &\ge d\,n\log_2 n+\Big(n-d\,n\log_2 3-d\log_2 n\Big). \end{align*}\]

Since \(\log_2 n\le n\), the term in parentheses is at least \(n\,(1-d\log_2 3-d)\), which is non-negative if

\[ d\le\frac{1}{1+\log_2 3}\approx 0.387. \]

We choose \(d=\frac{1}{4}\).

Base case (\(n=1\)): \(T(1)=1\ge \frac{1}{4}\cdot 1\cdot\log_2 1=0\). ✓

Observation 15.5: lower bound for \(2T(\lfloor n/2\rfloor)+n\)

The function \(T(n)\) defined in \(\eqref{eq:rec:subsMain}\) satisfies \(T(n)\ge \frac{1}{4}\,n\log_2 n\) for all \(n\ge 1\). Hence \(T(n)=\Omega(n\log_2 n)\).

Proof

By strong induction on \(n\ge 1\), with \(d=\frac{1}{4}\). For \(n=1\), \(T(1)=1\ge 0\). For \(n\ge 2\) we have \(1\le\lfloor n/2\rfloor<n\), so the inductive hypothesis holds for \(\lfloor n/2\rfloor\), and the computation of the inductive step above gives

\[ T(n)\ge \tfrac{1}{4}\,n\log_2 n+n\left(1-\tfrac{1}{4}\log_2 3-\tfrac{1}{4}\right)\ge \tfrac{1}{4}\,n\log_2 n , \]

since \(1-\frac{1}{4}(1+\log_2 3)\approx 0.35>0\). □

From Observations 15.4 and Observation 15.5, the solution of \(\eqref{eq:rec:subsMain}\) is

\[ T(n)=\Theta(n\log_2 n). \]

The floor does not change the order of growth found for \(n\) power of \(2\). Numerically, for every \(n\) with \(2\le n<200\,000\) the ratio \(\frac{T(n)}{n\log_2 n}\) lies between \(0.83\) and \(2\).

15.3.3 When the guess must be strengthened

• Sometimes the guess is correct, but the induction does not work because the inductive hypothesis is not strong enough. Consider

  \[\begin{equation*} T(n)= \begin{cases} 1 & \text{if } n=1\\ 2\,T\left(\lfloor n/2\rfloor\right)+1 & \text{if } n>1 \end{cases} \label{eq:rec:subsStrength} \tag{15.8} \end{equation*}\]

• For \(n\) power of \(2\) one easily finds \(T(n)=2n-1\) (for instance \(T(2)=3\), \(T(4)=7\), \(T(8)=15\)), so we guess \(T(n)=O(n)\), that is, \(T(n)\le c\,n\).

• Naive attempt. Substituting the guess,

  \[ T(n)\le 2\,c\,\lfloor n/2\rfloor+1\le c\,n+1, \]

  which does not imply \(T(n)\le c\,n\) for any choice of \(c\). The induction fails, by a lower-order term (the constant \(1\)).

• Strengthened guess. It is tempting to try a larger guess, such as \(c\,n^2\), but this is not needed. Instead, we subtract a lower-order term: we guess

  \[ T(n)\le c\,n-d, \]

  with \(d\ge 0\) a constant. Then

  \[ T(n)\le 2\big(c\,\lfloor n/2\rfloor-d\big)+1\le c\,n-2d+1\le c\,n-d, \]

  where the last step holds as long as \(d\ge 1\).

• Base case. \(T(1)=1\le c-d\): with \(d=1\) we need \(c\ge 2\).

Observation 15.6: strengthened guess for \(2T(\lfloor n/2\rfloor)+1\)

The function \(T(n)\) defined in \(\eqref{eq:rec:subsStrength}\) satisfies \(n\le T(n)\le 2n-1\) for all \(n\ge 1\). Hence \(T(n)=\Theta(n)\).

Proof

By strong induction on \(n\). For \(n=1\): \(1\le T(1)=1\le 2\cdot 1-1\). For \(n\ge 2\), we have \(1\le\lfloor n/2\rfloor<n\) and, by the inductive hypothesis, \(\lfloor n/2\rfloor\le T(\lfloor n/2\rfloor)\le 2\lfloor n/2\rfloor-1\).

Upper bound: \(T(n)\le 2\big(2\lfloor n/2\rfloor-1\big)+1=4\lfloor n/2\rfloor-1\le 2n-1\).

Lower bound: \(T(n)\ge 2\lfloor n/2\rfloor+1\ge (n-1)+1=n\). □

When the induction fails only because of a lower-order term, do not increase the guess: subtract a lower-order term from it (for example \(c\,n-d\) instead of \(c\,n\), or \(c\,n^2-d\,n\) instead of \(c\,n^2\)). The stronger hypothesis makes the induction work.

• Avoid pitfalls. In the naive attempt it would be wrong to conclude “\(T(n)\le c\,n+1=O(n)\), done”. The induction must prove exactly the form of the inductive hypothesis, \(T(n)\le c\,n\), with the same constant \(c\); otherwise the constant would grow at each step of the recursion.

15.3.4 Changing variables

Sometimes an algebraic manipulation, such as a change of variables, transforms an unknown recurrence into a known one, whose solution can then be reused.

Example 15.8: \(T(n)=2T(\lfloor\sqrt{n}\rfloor)+\log_2 n\)

Consider

\[ T(n)=2\,T\left(\lfloor\sqrt{n}\rfloor\right)+\log_2 n, \]

with boundary condition \(T(2)=1\).

• Step 1 (rename). Ignoring the rounding (that is, assuming that \(n=2^{2^k}\), so that all the square roots are exact powers of \(2\)), we rename \(m=\log_2 n\), that is, \(n=2^m\) and \(\sqrt{n}=2^{m/2}\):

  \[ T(2^m)=2\,T\left(2^{m/2}\right)+m. \]

• Step 2 (new function). We define \(R(m)=T(2^m)\) and obtain

  \[ R(m)=2\,R\left(\frac{m}{2}\right)+m, \]

  which is the recurrence of Example 15.7. Since \(T(2)=1\), we have \(R(1)=1\), and therefore

  \[ R(m)=m\log_2 m+m. \]

• Step 3 (back to \(T\)). With \(m=\log_2 n\):

  \[ T(n)=R(\log_2 n)=\log_2 n\cdot\log_2\log_2 n+\log_2 n=\Theta(\log_2 n\cdot\log_2\log_2 n). \]

Check: \(T(4)=2\,T(2)+2=4\) and \(R(2)=2\cdot 1+2=4\); \(T(16)=2\,T(4)+4=12\) and \(R(4)=4\cdot 2+4=12\).

15.4 The recursion-tree method

The substitution method proves a guess, but does not produce it. The recursion tree is the tool that produces good guesses, and in many cases it directly gives the solution.

• In a recursion tree, each node represents the cost of a single subproblem somewhere in the set of recursive function invocations. The children of a node are the subproblems generated by it.

• It can be used to solve recurrences, that is, to determine their asymptotic complexity, or to produce a good guess to be verified with the substitution method.

• Main idea: we sum the costs within each level of the tree to obtain a set of per-level costs, and then we sum all the per-level costs to determine the total cost of all the levels of the recursion.

In the recursion-tree method we determine:

1. the size of the subproblems and the number of nodes at each depth \(i\);

2. the cost of each level (number of nodes \(\times\) cost of each node);

3. the depth of the tree (when the subproblem size reaches the boundary condition) and the cost of the leaves;

4. the sum of the costs of all levels.

We apply the method to four recurrences, which show the three possible behaviours of the level costs (decreasing, constant, increasing) and the case of an unbalanced tree.

15.4.1 Decreasing level costs: \(T(n)=3T(n/4)+c\,n^2\)

• Consider the recurrence (\(c>0\) a constant)

  \[ T(n)=3\,T\left(\frac{n}{4}\right)+c\,n^2. \]

  For convenience, we assume that \(n\) is an exact power of \(4\), so that all subproblem sizes are integers.

Figure 15.1: Recursion tree of \(T(n)=3T(n/4)+c\,n^2\): every node has three children, the subproblem size is divided by \(4\) at each level, and the leaves are at depth \(\log_4 n\).

• The \(c\,n^2\) term at the root represents the cost at the top level of the recursion (dividing and combining).

• The three subtrees of the root represent the costs incurred by the subproblems of size \(\frac{n}{4}\); at the next depth the size becomes \(\frac{n}{16}\), and so on.

• The leaves represent the points where the recursion “bottoms out”, that is, where the base case of the recursion is reached.

Example 15.9: Solving \(T(n)=3T(n/4)+c\,n^2\) with the recursion tree

• Step 1 (sizes and nodes). The subproblem size of each node at depth \(i\) is \(\frac{n}{4^i}\). Each level has \(3\) times as many nodes as the previous level, so the number of nodes at depth \(i\) is \(3^i\).

• Step 2 (cost of a level). Each node at depth \(i\) (\(i=0,1,2,\dots,\log_4 n-1\)) has a cost of \(c\left(\frac{n}{4^i}\right)^2\). Multiplying, the overall cost of all the nodes at depth \(i\) is

  \[ 3^i\,c\left(\frac{n}{4^i}\right)^2=\left(\frac{3}{16}\right)^i c\,n^2. \]

• Step 3 (depth and leaves). The subproblem size reaches \(1\) when \(\frac{n}{4^i}=1\), that is, when \(i=\log_4 n\). Accordingly, the tree has \(\log_4 n+1\) levels (at depths \(0,1,2,\dots,\log_4 n\)). The bottom level has, using \(\eqref{eq:rec:logProps}\),

  \[ 3^{\log_4 n}=n^{\log_4 3} \]

  nodes (the leaves of the tree), each contributing a constant cost \(T(1)\). The total cost of the bottom level is

  \[ n^{\log_4 3}\,T(1)=\Theta\left(n^{\log_4 3}\right). \]

• Step 4 (sum). Summing up the costs of all levels we obtain

  \[\begin{align*} T(n) &= c\,n^2+\frac{3}{16}\,c\,n^2+\left(\frac{3}{16}\right)^2 c\,n^2+\cdots+\left(\frac{3}{16}\right)^{\log_4 n-1} c\,n^2+\Theta\left(n^{\log_4 3}\right)\\ &= \sum_{i=0}^{\log_4 n-1}\left(\frac{3}{16}\right)^i c\,n^2+\Theta\left(n^{\log_4 3}\right). \end{align*}\]

  Using the geometric series \(\eqref{eq:rec:geomFinite}\) we obtain the exact value

  \[ T(n)=\frac{16}{13}\left(1-\left(\frac{3}{16}\right)^{\log_4 n}\right)c\,n^2+\Theta\left(n^{\log_4 3}\right). \]

Upper bound. It is simpler to bound the finite sum by the infinite decreasing geometric series \(\eqref{eq:rec:geomInfinite}\):

\[\begin{align*} T(n) &< \sum_{i=0}^{\infty}\left(\frac{3}{16}\right)^i c\,n^2+\Theta\left(n^{\log_4 3}\right) = \frac{1}{1-\frac{3}{16}}\;c\,n^2+\Theta\left(n^{\log_4 3}\right)\\ &= \frac{16}{13}\;c\,n^2+\Theta\left(n^{\log_4 3}\right) = O(n^2), \end{align*}\]

since \(\log_4 3\approx 0.79<2\), so that \(n^{\log_4 3}=O(n^2)\).

Lower bound. All the terms of the sum are non-negative, and the root alone costs \(c\,n^2\). Hence

\[ T(n)\ge c\,n^2=\Omega(n^2). \]

Numerical check (\(c=1\), \(T(1)=1\)): the recurrence gives \(T(4)=19\), \(T(16)=313\), \(T(64)=5035\), the values of the exact formula above, and \(\frac{T(n)}{n^2}=1.1875,\ 1.2227,\ 1.2292\), which approach \(\frac{16}{13}\approx 1.2308\).

The solution of \(T(n)=3T(n/4)+c\,n^2\) is \(T(n)=\Theta(n^2)\). The costs of the levels decrease geometrically: the total cost is dominated by the cost of the root.

15.4.2 Constant level costs: \(T(n)=2T(n/2)+c\,n\)

• Consider the recurrence (\(c>0\) a constant), which describes algorithms such as MergeSort:

  \[ T(n)=2\,T\left(\frac{n}{2}\right)+c\,n, \]

  where \(n\) is an exact power of \(2\).

Figure 15.2: Recursion tree of \(T(n)=2T(n/2)+c\,n\): every level has total cost \(c\,n\).

Example 15.10: Solving \(T(n)=2T(n/2)+c\,n\) with the recursion tree

• Steps 1 and 2. At depth \(i\) there are \(2^i\) nodes, each corresponding to a subproblem of size \(\frac{n}{2^i}\) and with cost \(c\,\frac{n}{2^i}\). The cost of each level is therefore

  \[ 2^i\,c\,\frac{n}{2^i}=c\,n. \]

• Step 3. The subproblem size reaches \(1\) at depth \(\log_2 n\). The bottom level has \(2^{\log_2 n}=n\) leaves, with total cost \(n\,T(1)=\Theta(n)\).

• Step 4. Summing the costs of all levels:

  \[ T(n)=\sum_{i=0}^{\log_2 n-1}c\,n+n\,T(1)=c\,n\log_2 n+n\,T(1)=\Theta(n\log_2 n). \]

For \(c=1\) and \(T(1)=1\) we obtain again \(T(n)=n\log_2 n+n\) (Example 15.7).

The solution of \(T(n)=2T(n/2)+c\,n\) is \(T(n)=\Theta(n\log_2 n)\). All the levels have the same cost \(c\,n\), and there are \(\Theta(\log_2 n)\) levels.

15.4.3 An unbalanced tree: \(T(n)=T(n/3)+T(2n/3)+c\,n\)

• Consider the recurrence (\(c,d>0\) constants), defined for every real number \(n>0\):

  \[ T(n)= \begin{cases} d & \text{if } 0<n<1\\ T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+c\,n & \text{if } n\ge 1 \end{cases} \]

  (Working with real sizes allows us to avoid floors and ceilings.)

Figure 15.3: Recursion tree of \(T(n)=T(n/3)+T(2n/3)+c\,n\): the shortest root-to-leaf path (blue) has length about \(\log_3 n\), the longest (red) about \(\log_{3/2} n\).

• Each internal node of size \(s\) has two children of sizes \(\frac{s}{3}\) and \(\frac{2s}{3}\), whose sum is \(s\). Hence the sizes of the nodes at any given depth sum to at most \(n\) (exactly \(n\) if the level is complete).

• The shortest path from the root to a leaf is the leftmost one: \(n\to\frac{n}{3}\to\frac{n}{9}\to\cdots\). A node at depth \(i\) on this path has size \(\frac{n}{3^i}\), which is \(\ge 1\) as long as \(i\le\log_3 n\).

• The longest path is the rightmost one: \(n\to\frac{2n}{3}\to\frac{4n}{9}\to\cdots\). A node at depth \(i\) on this path has size \(\left(\frac{2}{3}\right)^i n\), which is \(\ge 1\) as long as \(i\le\log_{3/2} n\).

• Unlike the previous examples, the tree is not complete: the leaves are at different depths, between \(\log_3 n\) and \(\log_{3/2} n\) (approximately).

Example 15.11: Bounds for the unbalanced tree

Upper bound.

• Internal nodes. Every node at depth \(i\) has size at most \(\left(\frac{2}{3}\right)^i n\); an internal node has size \(\ge 1\), so internal nodes appear only at depths \(i\le\log_{3/2} n\). At each depth, the internal nodes have total size at most \(n\), so their total cost is at most \(c\,n\). Hence the cost of the internal nodes is at most

  \[ c\,n\left(\log_{3/2} n+1\right). \]

• Leaves. A leaf has size \(<1\), but its parent has size \(\ge 1\), so a leaf has size \(\ge\frac{1}{3}\). The sizes of all the leaves sum to exactly \(n\) (each internal node splits its size among its children). Hence there are at most \(3n\) leaves, with total cost at most \(3\,d\,n=O(n)\).

• Therefore

  \[ T(n)\le c\,n\left(\log_{3/2} n+1\right)+3\,d\,n=O(n\log_2 n), \]

  since \(\log_{3/2} n=\frac{\log_2 n}{\log_2(3/2)}\) differs from \(\log_2 n\) by a constant factor \(\eqref{eq:rec:logProps}\).

Lower bound.

• Every node at depth \(i\) has size at least \(\frac{n}{3^i}\). Hence, for every depth \(i\le\log_3 n\), all the nodes at depth \(i\) have size \(\ge 1\): they are internal nodes, the level is complete (\(2^i\) nodes) and their sizes sum to exactly \(n\). The cost of each of these levels is exactly \(c\,n\).

• There are \(\lfloor\log_3 n\rfloor+1\ge\log_3 n\) such levels (depths \(0,1,\dots,\lfloor\log_3 n\rfloor\)), so

  \[ T(n)\ge c\,n\log_3 n=\Omega(n\log_2 n). \]

Numerical check (\(c=d=1\)): computing \(T(n)\) exactly from the recurrence, \(T(100)\approx 929.2\) and \(T(1000)\approx 13\,002.3\); both values lie between the lower bound \(n\log_3 n\) (\(419.2\) and \(6\,287.7\)) and the upper bound \(n(\log_{3/2} n+1)+3n\) (\(1\,535.8\) and \(21\,036.6\)).

The solution of \(T(n)=T(n/3)+T(2n/3)+c\,n\) is \(T(n)=\Theta(n\log_2 n)\). Each level costs at most \(c\,n\); the upper bound uses the longest path (\(\log_{3/2} n\)) and the lower bound uses the shortest path (\(\log_3 n\)). Both are \(\Theta(\log_2 n)\).

• Remark. If the tree were a complete binary tree of height \(\log_{3/2} n\), it would have \(2^{\log_{3/2} n}=n^{\log_{3/2} 2}\approx n^{1.71}\) leaves, which is \(\omega(n\log_2 n)\). The argument above shows that the tree is far from complete: the actual number of leaves is \(O(n)\). When the leaves are not easy to count, a safe approach is to use the recursion tree only to guess the solution and then to prove it with the substitution method.

15.4.4 Increasing level costs: \(T(n)=4T(n/2)+n\)

Example 15.12: Solving \(T(n)=4T(n/2)+n\) with the recursion tree

Consider the recurrence

\[ T(n)= \begin{cases} 1 & \text{if } n=1\\ 4\,T\left(\frac{n}{2}\right)+n & \text{if } n>1 \end{cases} \]

where \(n\) is an exact power of \(2\).

• Steps 1 and 2. At depth \(i\) there are \(4^i\) nodes, each of size \(\frac{n}{2^i}\) and cost \(\frac{n}{2^i}\). The cost of the level is

  \[ 4^i\,\frac{n}{2^i}=2^i\,n. \]

• Step 3. The size reaches \(1\) at depth \(\log_2 n\), where there are \(4^{\log_2 n}=n^2\) leaves:

  depth	number of nodes	cost of each node	cost of the level
  \(0\)	\(1\)	\(n\)	\(n\)
  \(1\)	\(4\)	\(n/2\)	\(2n\)
  \(2\)	\(16\)	\(n/4\)	\(4n\)
  \(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
  \(i\)	\(4^i\)	\(n/2^i\)	\(2^i n\)
  \(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
  \(\log_2 n\)	\(4^{\log_2 n}=n^2\)	\(T(1)=1\)	\(n^2\)

• Step 4. The costs increase geometrically going down the tree. Using \(\eqref{eq:rec:geomTwo}\),

  \[ T(n)=\sum_{i=0}^{\log_2 n-1}2^i\,n+n^2=n\left(2^{\log_2 n}-1\right)+n^2=n(n-1)+n^2=2n^2-n. \]

Hence \(T(n)=2n^2-n=\Theta(n^2)\): indeed \(\lim_{n\to\infty}\frac{2n^2-n}{n^2}=2\in\R_{>0}\). Check: \(T(2)=4+2=6\), \(T(4)=24+4=28\), \(T(8)=112+8=120=2\cdot 64-8\).

The solution of \(T(n)=4T(n/2)+n\) is \(T(n)=\Theta(n^2)\). The costs of the levels increase geometrically: the total cost is dominated by the leaves, whose number is \(4^{\log_2 n}=n^{\log_2 4}=n^2\).

15.5 Towards the Master Theorem

The three balanced trees of the previous section are instances of the same picture. We now draw the recursion tree of a general recurrence in standard form \(\eqref{eq:rec:standardForm}\)

\[ T(n)= \begin{cases} \Theta(1) & \text{if } n=1\\ a\,T\left(\frac{n}{b}\right)+f(n) & \text{if } n>1 \end{cases} \]

with \(a\ge 1\), \(b>1\) constants and \(n\) an exact power of \(b\).

Figure 15.4: Recursion tree of a recurrence in standard form \(T(n)=a\,T(n/b)+f(n)\), for \(n\) exact power of \(b\).

• At depth \(j\) there are \(a^j\) nodes, each corresponding to a subproblem of size \(\frac{n}{b^j}\) with cost \(f\left(\frac{n}{b^j}\right)\). The cost of the level is

  \[ a^j\,f\left(\frac{n}{b^j}\right). \]

• The subproblem size reaches \(1\) at depth \(\log_b n\). The number of leaves is, by \(\eqref{eq:rec:logProps}\),

  \[ a^{\log_b n}=n^{\log_b a}, \]

  and their total cost is \(\Theta\left(n^{\log_b a}\right)\).

• Summing the costs of all levels:

  \[\begin{equation*} T(n)=\Theta\left(n^{\log_b a}\right)+\sum_{j=0}^{\log_b n-1}a^j\,f\left(\frac{n}{b^j}\right). \label{eq:rec:generalTree} \tag{15.9} \end{equation*}\]

• The solution depends on how the level costs \(a^j f(n/b^j)\) evolve with \(j\), that is, on the comparison between \(f(n)\) (the cost of the root) and \(n^{\log_b a}\) (the cost of the leaves). There are three possible behaviours, all of which we have already met:

  1. The leaves dominate: the level costs increase geometrically going down the tree, and \(T(n)=\Theta\left(n^{\log_b a}\right)\).

     Example: \(T(n)=4T(n/2)+n\), with \(n^{\log_2 4}=n^2\) leaves, \(T(n)=\Theta(n^2)\) (Example 15.12).

  2. All levels have (about) the same cost: the cost of each of the \(\log_b n+1\) levels is \(\Theta\left(n^{\log_b a}\right)\), and \(T(n)=\Theta\left(n^{\log_b a}\log_2 n\right)\).

     Example: \(T(n)=2T(n/2)+c\,n\), with \(n^{\log_2 2}=n\), \(T(n)=\Theta(n\log_2 n)\) (Example 15.10).

  3. The root dominates: the level costs decrease geometrically going down the tree, and \(T(n)=\Theta(f(n))\).

     Example: \(T(n)=3T(n/4)+c\,n^2\), with \(f(n)=c\,n^2\), \(T(n)=\Theta(n^2)\) (Example 15.9).

The Master Theorem, studied in the chapter The Master Theorem, makes these three behaviours precise. It compares \(f(n)\) with \(n^{\log_b a}\) and gives the solution of a recurrence in standard form directly, without drawing the recursion tree.

15.6 Summary: which method when

• Expansion method: recurrences with a single recursive term, for example \(T(n-1)+f(n)\), \(2T(n-1)+1\), \(T(n/2)+c\), \(2T(n/2)+n\). It gives the exact closed form when the resulting summation can be computed (arithmetic or geometric series).

• Substitution method: when we have a guess and want a rigorous proof, in particular with floors and ceilings and explicit boundary conditions. Prove \(O\) and \(\Omega\) separately; handle the base cases by choosing \(n_0\); if the induction fails by a lower-order term, subtract a lower-order term from the guess. It can be combined with a change of variables.

• Recursion-tree method: to visualise the costs and to obtain a guess; ideal when the recursive terms have different sizes (unbalanced trees, as \(T(n/3)+T(2n/3)+c\,n\)). Compute the cost per level, the depth, the number of leaves, and sum using the geometric series.

• Master Theorem (chapter The Master Theorem): recurrences in standard form \(a\,T(n/b)+f(n)\); it gives the answer directly by comparing \(f(n)\) with \(n^{\log_b a}\). It does not apply to \(T(n-1)+f(n)\) or to unbalanced splits.

---

Exercises on this chapter: Recurrences