21.4: Divide-and-Conquer Recurrences

We now have a recipe for solving general linear recurrences. But the Merge Sort recurrence, which we encountered earlier, is not linear:

\[\begin{aligned} T(1) &= 0 \\ T(n) &= 2T(n / 2) + n - 1 & (\text{for } n \geq 2). \end{aligned}\]

In particular, \(T(n)\) is not a linear combination of a fixed number of immediately preceding terms; rather, \(T(n)\) is a function of \(T(n / 2)\), a term halfway back in the sequence.

Short Guide to Solving Linear Recurrences

A linear recurrence is an equation

\[ \nonumber f(n) = \underbrace{a_1 f(n - 1) + a_2 f(n - 2) + \cdots + a_d f(n - d)}_{\text{homogeneous part}} \underbrace{+ g(n)}_{\text{inhomogeneous part}}\]

together with boundary conditions such as \(f(0) = b_0, f(1) = b_1\), etc. Linear recurrences are solved as follows:

1. Find the roots of the characteristic equation

\[\nonumber x^n = a_1 x^{n-1} + a_2 x^{n-2} + \cdot + a_k x^{n-k}.\]

2. Write down the homogeneous solution. Each root generates one term and the homogeneous solution is their sum. A nonrepeated root \(r\) generates the term \(cr^n\), where \(c\) is a constant to be determined later. A root \(r\) with multiplicity \(k\) generates the terms

\[\nonumber d_1 r^n \quad d_2nr^n \quad d_2n^2r^n \quad \ldots \quad d_kn^{k-1}r^n\]

where \(d_1, \ldots, d_k\) are constants to be determined later.

3. Find a particular solution. This is a solution to the full recurrence that need not be consistent with the boundary conditions. Use guess-and-verify. If \(g(n)\) is a constant or a polynomial, try a polynomial of the same degree, then of one higher degree, then two higher. For example, if \(g(n) = n\), then try \(f(n) = bn + c\) and then \(an^2 + bn + c\). If \(g(n)\) is an exponential, such as \(3^n\), then first guess \(f(n) = c3^n\). Failing that, try \(f(n) = (bn + c)3^n\) and then \((an^2 + bn + c) 3^n\), etc.

4. Form the general solution, which is the sum of the homogeneous solution and the particular solution. Here is a typical general solution:

\[ \nonumber f(n) = \underbrace{c2^n + d(-1)^n}_{\text{homogeneous solution}} + \underbrace{3n + 1}_{\text{inhomogeneous solution}}\]

5. Substitute the boundary conditions into the general solution. Each boundary condition gives a linear equation in the unknown constants. For example, substituting \(f(1) = 2\) into the general solution above gives

\[\begin{aligned} 2 &= c \cdot 2^1 + d \cdot (-1)^1 + 3 \cdot 1 + 1 \\ \text{IMPLIES} \quad -2 &= 2c - d. \end{aligned}\]

Determine the values of these constants by solving the resulting system of linear equations.

Merge Sort is an example of a divide-and-conquer algorithm: it divides the input, “conquers” the pieces, and combines the results. Analysis of such algorithms commonly leads to divide-and-conquer recurrences, which have this form:

\[\nonumber T(n) = \sum_{i = 1}^{k} a_i T(b_i n) + g(n)\]

Here \(a_1, \ldots, a_k\) are positive constants, \(b_1, \ldots, b_k\) are constants between 0 and 1, and \(g(n)\) is a nonnegative function. For example, setting \(a_1 = 2, b_1 = 1/2\), and \(g(n) = n - 1\) gives the Merge Sort recurrence.

The Akra-Bazzi Formula

The solution to virtually all divide and conquer solutions is given by the amazing Akra-Bazzi formula. Quite simply, the asymptotic solution to the general divideand-conquer recurrence

\[\nonumber T(n) = \sum_{i = 1}^{k} a_i T(b_i n) + g(n)\]

is

\[T(n) = \Theta \left( n^p \left( 1 + \int_{1}^{n} \frac{g(u)}{u^{p+1}} du\right) \right)\]

where \(p\) satisfies

\[\sum_{i = 1}^{k} a_i b_i^p = 1.\]

A rarely-troublesome requirement is that the function \(g(n)\) must not grow or oscillate too quickly. Specifically, \(|g' (n)|\) must be bounded by some polynomial. So, for example, the Akra-Bazzi formula is valid when \(g(n) = x^2 \log n\), but not when \(g(n) = 2^n\).

Let’s solve the Merge Sort recurrence again, using the Akra-Bazzi formula instead of plug-and-chug. First, we find the value \(p\) that satisfies

\[\nonumber 2 \cdot (1/2)^p = 1.\]

Looks like \(p = 1\) does the job. Then we compute the integral:

\[\begin{aligned} T(n) &= \Theta \left( n \left( 1 + \int_{1}^{n} \frac{u - 1}{u^2} du\right) \right) \\ &= \Theta \left( n \left( 1 + \left[ \log u + \frac{1}{u}\right]_{1}^{n} \right) \right) \\ &= \Theta \left( n \left( \log n + \frac{1}{n} \right) \right) \\ &= \Theta (n \log n) \end{aligned}\]

The first step is integration and the second is simplification. We can drop the \(1/n\) term in the last step, because the \(\log n\) term dominates. We’re done!

Let’s try a scary-looking recurrence:

\[\nonumber T(n) = 2T(n / 2) + (8/9)T(3n / 4) + n^2.\]

Here, \(a_1 = 2, b_1 = 1/2, a_2 = 8/9,\) and \(b_2 = 3/4\). So we find the value \(p\) that satisfies

\[\nonumber 2 \cdot (1/2)^p + (8/9)(3/4)^p =1. \]

Equations of this form don’t always have closed-form solutions, so you may need to approximate \(p\) numerically sometimes. But in this case the solution is simple: \(p = 2\). Then we integrate:

\[\begin{aligned} T(n) &= \Theta \left( n^2 \left( 1 + \int_{1}^{n} \frac{u^2}{u^3} du\right) \right) \\ &= \Theta(n^2 (1 + \log n)) \\ &= \Theta (n^2 \log n). \end{aligned}\]

That was easy!

Two Technical Issues

Until now, we’ve swept a couple issues related to divide-and-conquer recurrences under the rug. Let’s address those issues now.

First, the Akra-Bazzi formula makes no use of boundary conditions. To see why, let’s go back to Merge Sort. During the plug-and-chug analysis, we found that

\[\nonumber T_n = nT_1 + n \log n - n + 1.\]

This expresses the nth term as a function of the first term, whose value is specified in a boundary condition. But notice that \(T_n = \Theta(n \log n)\) for every value of \(T_1\). The boundary condition doesn’t matter!

This is the typical situation: the asymptotic solution to a divide-and-conquer recurrence is independent of the boundary conditions. Intuitively, if the bottomlevel operation in a recursive algorithm takes, say, twice as long, then the overall running time will at most double. This matters in practice, but the factor of 2 is concealed by asymptotic notation. There are corner-case exceptions. For example, the solution to \(T(n) = 2T(n / 2)\) is either \(\Theta(n)\) or zero, depending on whether \(T(1)\) is zero. These cases are of little practical interest, so we won’t consider them further.

There is a second nagging issue with divide-and-conquer recurrences that does not arise with linear recurrences. Specifically, dividing a problem of size \(n\) may create subproblems of non-integer size. For example, the Merge Sort recurrence contains the term \(T(n / 2)\). So what if \(n\) is 15? How long does it take to sort sevenand-a-half items? Previously, we dodged this issue by analyzing Merge Sort only when the size of the input was a power of 2. But then we don’t know what happens for an input of size, say, 100.

Of course, a practical implementation of Merge Sort would split the input approximately in half, sort the halves recursively, and merge the results. For example, a list of 15 numbers would be split into lists of 7 and 8. More generally, a list of n numbers would be split into approximate halves of size \(\lceil n / 2 \rceil\) and \(\lfloor n / 2 \rfloor\). So the maximum number of comparisons is actually given by this recurrence:

\[\begin{aligned} T(1) &= 0 \\ T(n) &= T(\lceil n / 2 \rceil) + T(\lfloor n / 2 \rfloor) + n - 1 & (\text{for } n \geq 2). \end{aligned}\]

This may be rigorously correct, but the ceiling and floor operations make the recurrence hard to solve exactly.

Fortunately, the asymptotic solution to a divide and conquer recurrence is unaffected by floors and ceilings. More precisely, the solution is not changed by replacing a term \(T(b_i n)\) with either \(T(\lceil b_i n \rceil)\) or \(T(\lfloor b_i n \rfloor)\). So leaving floors and ceilings out of divide-and-conquer recurrences makes sense in many contexts; those are complications that make no difference.

The Akra-Bazzi Theorem

The Akra-Bazzi formula together with our assertions about boundary conditions and integrality all follow from the Akra-Bazzi Theorem, which is stated below.

Theorem \(\PageIndex{1}\)

(Akra-Bazzi). Suppose that the function \(T : \mathbb{R} \rightarrow \mathbb{R}\) is nonnegative and bounded for \(0 \leq x \leq x_0\) and satisfies the recurrence

\[T(x) \sum_{i = 1}^{k} a_i T (b_i x + h_i(x)) + g(x) \quad \textit{for } x > x_0,\]

where:

1. \(x_0\) is large enough so that \(T\) is well-defined,
2. \(a_1,\ldots, a_k\) are positive constants,
3. \(b_1,\ldots, b_k\) are constants between 0 and 1,
4. \(g(x)\) is a nonnegative function such that \(|g'(x)|\) is bounded by a polynomial,
5. \(|h_i(x)| = O(x / \log^2 x)\).

Then

\[\nonumber T(x) = \Theta \left( x^p \left( 1 + \int_{1}^{x} \frac{g(u)}{u^{p+1}} du\right) \right)\]

where \(p\) satisfies

\[\nonumber \sum_{i = 1}^{k}a_i b_i^p = 1.\]

The Akra-Bazzi theorem can be proved using a complicated induction argument, though we won’t do that here. But let’s at least go over the statement of the theorem.

All the recurrences we’ve considered were defined over the integers, and that is the common case. But the Akra-Bazzi theorem applies more generally to functions defined over the real numbers.

The Akra-Bazzi formula is lifted directed from the theorem statement, except that the recurrence in the theorem includes extra functions, \(h_i\). These functions extend the theorem to address floors, ceilings, and other small adjustments to the sizes of subproblems. The trick is illustrated by this combination of parameters

\[\nonumber \begin{array}{ccc} a_1 = 1 & b_1 = 1/2 & h_1(x) = \lceil \frac{x}{2} \rceil - \frac{x}{2}\\ a_2 = 1 & b_2 = 1/2 & h_2(x) = \lfloor \frac{x}{2} \rfloor - \frac{x}{2}\\ & g(x) = x - 1 &\end{array}\]

which corresponds the recurrence

\[\begin{aligned} T(x) &= 1 \cdot T \left( \frac{x}{2} + \left( \big\lceil \frac{x}{2} \big\rceil - \frac{x}{2} \right)\right) + \cdot T \left( \frac{x}{2} + \left( \big\lfloor \frac{x}{2} \big\rfloor - \frac{x}{2} \right)\right) + x - 1 \\ &= T\left( \big\lceil \frac{x}{2} \big\rceil \right) + T \left( \big\lfloor \frac{x}{2} \big\rfloor \right) + x - 1. \end{aligned}\]

This is the rigorously correct Merge Sort recurrence valid for all input sizes, complete with floor and ceiling operators. In this case, the functions \(h_1(x)\) and \(h_2(x)\) are both at most 1, which is easily \(O(x / \log^2 x)\) as required by the theorem statement. These functions \(h_i\) do not affect—or even appear in—the asymptotic solution to the recurrence. This justifies our earlier claim that applying floor and ceiling operators to the size of a subproblem does not alter the asymptotic solution to a divide-and-conquer recurrence.

The Master Theorem

There is a special case of the Akra-Bazzi formula known as the Master Theorem that handles some of the recurrences that commonly arise in computer science. It is called the Master Theorem because it was proved long before Akra and Bazzi arrived on the scene and, for many years, it was the final word on solving divideand-conquer recurrences. We include the Master Theorem here because it is still widely referenced in algorithms courses and you can use it without having to know anything about integration.

Theorem \(\PageIndex{1}\)

(Master Theorem). Let \(T\) be a recurrence of the form

\[\nonumber T(n) = aT \left( \frac{n}{b}\right) + g(n).\]

Case 1: If \(g(n) = O \left( n^{\log_b (a) - \epsilon} \right)\) for some constant \(\epsilon > 0\), then

\[\nonumber T(n) = \Theta \left( n^{\log_b (a)} \right).\]

Case 2: If \(g(n) = O \left( n^{\log_b (a)} \log^k (n) \right)\) for some constant \(k > 0\), then

\[\nonumber T(n) = \Theta \left( n^{\log_b (a)} \log^{k+1} (n) \right).\]

Case 3: If \(g(n) = \Omega \left( n^{\log_b (a) + \epsilon}\right)\) for some constant \(\epsilon > 0\) and \(ag(n / b) < cg(n)\) for some constant \(c<1\) and sufficiently large \(n\), then

\[\nonumber T(n) = \Theta(g(n)).\]

The Master Theorem can be proved by induction on \(n\) or, more easily, as a corollary of Theorem 21.4.1. We will not include the details here.