Lecture 20: Solving Recurrences

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \DeclareMathOperator{\Pr}{Pr} \DeclareMathOperator{\rng}{rng} \DeclareMathOperator{\E}{E} \DeclareMathOperator{\V}{V} \DeclareMathOperator{\T}{T} \DeclareMathOperator{\O}{O} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \)

This material follows Cormen, Leiserson, Rivest, and Stein, “Introduction to Algorithms (3rd Edition),” Chapter 4.

One of the most common motifs in the design of algorithms is “divide and conquer.”

Example 20.1 (Merge sort) To sort a list of $n$ elements for $n>1$, we can divide it into two halves, sort each half, and merge the results:

Merge sort illustration.

Of course, there was much undefined in our original sketch, e.g., how to split the top level list (in this case, we simply dealt the elements of the list of size $n$ out to the sublists), and how to merge. Still, we feel fairly comfortable giving a rough and ready analysis.

We want to compute the overall complexity of sorting $n$ elements, a quantity that we'll describe as $\T(n)$.

The split phase requires that we consider each element of the list, but we only have to do a constant amount of work per element (assuming we made reasonable representation and implementation choices), so this is $\Theta(n)$.

The sort phases involve sorting two lists of size roughly $n/2$, i.e., $2 \T(n/2)$. If we're feeling particularly fastidious, we might phrase this as $\T(\ceiling{n/2}) + \T(\floor{n/2})$, as $n$ need not be even.

Finally, the merge phase (again, assuming reasonable representation and implementation choices) will take time $\Theta(n)$.

And of course, the recursion here “bottoms out” at $n=1$ (or even $n=0$), and this takes some time, but we'll assume it's a constant.

What then can we say about $\T(n)$?

Example 20.2 The usual high-school algorithm for multiplying two $n \times n$ matrices requires time $O(n^3)$: we have to compute $n^2$ entries, and the computation of each entry requires summing the result of $n$ products. A cute observation is that we can multiply hierarchically, i.e., we can view a $2n \times 2n$ matrix as a $2 \times 2$ array of $n \times n$ arrays

\begin{equation*} \left[ \begin{array}{c|c} A & B\\ \hline C & D \end{array} \right] \end{equation*}

and then do a $2\times 2$ product of $n \times n$ matrices

\begin{equation*} \left[ \begin{array}{c|c} A & B\\ \hline C & D \end{array} \right] \times \left[ \begin{array}{c|c} E & F\\ \hline G & H \end{array} \right] = \left[ \begin{array}{c|c} AE + BG & AF + BH\\ \hline CE + DG & CF + DH \end{array} \right] \end{equation*}

This gives rise to an analysis in which $\T(n) = 8 \T(n/2) + \Theta(n^2)$. Soon enough, we'll be able to see that $T(n)$ is $\O(n^3)$, which is not surprising, because this approach does all of the same multiplications as the high school algorithm, it thinks about them a different way. But an extremely clever variant of this (Strassen's algorithm) builds 10 linear combinations of the matrices $A,\ldots,H$, and then creates seven products of these, and shows that all of the eight required products can be formed as fixed linear combinations of seven product matrices. This gives rise to an analysis in which $\T(n) = 7 \T(n/2) + \Theta(n^2)$. What can we say about that?

A Basic Framework

We can generalize from the specific examples above, and the general structure of divide and conquer algorithms, to a particular form of recurrence that often appears:

\begin{equation*} \T(n) = a \mult \T(n/b) + f(n) \end{equation*}

where $f(n)$ may be expressed asymptotically (i.e., using either $O$, $\Omega$, or $\Theta$.

Obviously, if $f$ is expressed asymptotically, we're not going to be able to give an exact answer, but we can hope to answer a $\Theta$ with a $\Theta$, a big-$\O$ with a big-$\O$, and an $\Omega$ with an $\Omega$. Likewise, sometimes we're not given an equality, but an inequality, e.g.,

\begin{equation*} \T(n) \leq a \mult \T(n/b) + f(n) \end{equation*}

In such cases, we can hope for upper bounds (or lower bounds, in the case of $\geq$), but not exact results.

Substitution

This is just a fancy name for “guess and check,” albeit moderated by the presence of parameters we can set in order to make the recurrence hold.

Let's begin by considering a simple, unfussy case, $f(n) = 0$, i.e., $\T(n) = a \T(n/b)$ for $a,b > 1$, without worrying about whether the division in $n/b$ results in an integral value. A natural guess (at least, if you've been around the block a couple times) is $\T(n) = c n^d$, where the parameters $c$ and $d$ are to be determined. If we substitute this into the recurrence, we get

\begin{align*} c n^d &= a c \left({n\over b}\right)^d \\ &= c n^d \left({a \over b^d}\right) \end{align*}

which, after dividing by $c n^d$ leaves us with

\begin{align*} 1 &= {a \over b^d}\\ b^d &= a\\ \log_b b^d &= \log_b a\\ d &= \log_b a \\ \end{align*}

Thus, if we consider “relaxed” versions of the earlier recurrences, we get, for $\T(n) = 2\T(n/2)$, the solution $\T(n) = c n$, and for $\T(n) = 7 \T(n/2)$ the solution $\T(n) = n^{\log 7\over \log 8} = n^{2.807...}$, which is certainly better than $n^3$. And, we still have the freedom to choose $c$, and the natural choice is $T(1)$, which often gets written (with a combination of convenience and prescience) as $\Theta(1)$.

This doesn't permit a solution in cases where $f(n) \not= 0$, but it does give us useful intuition in dealing with more complicated cases.

Some examples

Example 20.3 $\T(n) = T(n/2) + 1$. This is essentially the complexity analysis of binary search: given a sorted array of items $a$, and a value $x$, determine whether or not $x \in a$ by repeatedly dividing our search region in half.

We can approach this naturally, not by guess and check, but by iterated replacement:

\begin{align*} \T(n) &= T(n/2) + 1\\ &= T(n/2^2) + 2 \\ &= T(n/2^3) + 3 \\ &\ldots\\ &= T(n/2^k) + k\\\ \end{align*}

If we set $k=\log_2 n$, we get

\begin{align*} T(n) &= T(1) + \log_2 n \\ &= \Theta(\log n) \end{align*}

Note that when we pass to $\Theta$ notation, the base of the logarithms no longer matters...

Example 20.4 $\T(n) = \T(n/2) + n$. This corresponds to a rough analysis of a very nice probabilistic algorithm for finding the $k$-th largest element of an unordered list. We could approach this by sorting and indexing, which would require $\O(n \log n)$ time for the sort phase, and constant time for indexing. But we can do better. Grab a random element, and divide the list roughly in half, according to whether each element is larger or smaller than the “pivot.” We can then recurse (possibly adjusting $k$) down to one list or the other.

We'll approach this much as the last example:

\begin{align*} \T(n) &= T(n/2) + n\\ &= T(n/2^2) + n/2 + n \\ &= T(n/2^3) + n/2^2 + n/2 +n \\ &\ldots\\ &= T(n/2^k) + n \sum_{j=0}^{k-1} {1\over 2^j}\\ \end{align*}

Again, choosing $k=\log_2 n$, and replacing the finite sum with the corresponding infinite sum, yields

\begin{align*} \T(n) &= \Theta(T(1) + 2n)\\ &= \Theta(n) \end{align*}

Example 20.5 $\T(n)=2\T(n/2)+n$. This is essentially the merge sort algorithm.

Again, we'll unwind the recurrence seeking inspiration

\begin{align*} \T(n) &= 2 \mult \T(n/2) + n\\ &= 2^2 \mult \T(n/2^2) + 2\mult n \\ &= 2^3 \mult \T(n/2^3) + 3\mult n \\ &\ldots\\ &= 2^k \mult \T(n/2^k) + k\mult n \end{align*}

And again, choosing $k=\log_2 n$ gives us the estimate we're looking for:

\begin{align*} \T(n) &= n \mult T(1) + n \log_2 n\\ &= \Theta(n \log n)\\ \end{align*}

Example 20.6 $\T(n) = 3 \T(n/2) + n$. Let's think of this as a simpler version of the Strassen recurrence.

We know from the work above that $c \mult n^{\log_2 3} = c \mult n^{1.5849\ldots}$ is a solution to the simple recurrence $\T(n) = 3 \T(n/2)$. Because $1.5859\ldots \gt 1$, where $1$ is the exponent of the “inhomogeneous” term $n$, we expect to find a solution of the form $c \mult n^{\log_2 3} + \Theta(n)$. To that end, we'll substitute $c_1 \mult n^{\log_2 3} + c_2 n$ in for $\T(n)$, giving us

\begin{align*} c_1 \mult n^{\log_2 3} + c_2 n &= 3 (c_1 \mult (n/2)^{\log_2 3} + c_2 n/2) + n\\ c_1 \mult n^{\log_2 3} + c_2 n &= c_1 \mult n^{\log_2 3} + 3 c_2 n/2 + n\\ c_2 n &= {3/2} c_2 n + n\\ c_2 &= {3/2} c_2 + 1\\ -{1\over 2} c_2 &= 1\\ c_2 &= -2 \end{align*}

Thus, our solution has the form

\begin{align*} \T(n) &= c \mult n^{\log_2 3} - 2 n\\ &= \Theta(n^{\log_2 3}) \end{align*}

*Exercise 20.7 Complete the asymptotic analysis of Strassen's algorithm, showing $T(n)$ is $\Theta(n^{\log_2 7})$.

The Master Method

Examples like this can be generalized, enabling us to give useful asymptotic analyses of recurrences of the form $\T(n) = a T(n/b) + f(n)$ for various $f$:

We can think of the master method as saying that if the recurrence beats the inhomogeneous term, then we're essentially in the simple case, and if the inhomogeneous term beats the recurrence, then we're essentially at the inhomogeneous term, and if they're tied, we get an extra log factor.

The proof of the master method (in generality) takes more time than we have, but it's a useful as a way of informing our approach to special cases.