Close
Register
Close Window

Show Source |    | About   «  21.7. Summation Techniques   ::   Contents   ::   22.1. Chapter Introduction: Search  »

21.8. Solving Recurrence Relations

21.8.1. Solving Recurrence Relations

Todo

type: Equation cross-reference

Throughout this module, there are references to equations, both on this page and in the Summations module. These should be made into proper cross-references rather than hard-coded equation numbers.

Recurrence relations are often used to model the cost of recursive functions. For example, the standard Mergesort takes a list of size \(n\), splits it in half, performs Mergesort on each half, and finally merges the two sublists in \(n\) steps. The cost for this can be modeled as

\[{\bf T}(n) = 2{\bf T}(n/2) + n.\]

In other words, the cost of the algorithm on input of size \(n\) is two times the cost for input of size \(n/2\) (due to the two recursive calls to Mergesort) plus \(n\) (the time to merge the sublists together again).

There are many approaches to solving recurrence relations, and we briefly consider three here. The first is an estimation technique: Guess the upper and lower bounds for the recurrence, use induction to prove the bounds, and tighten as required. The second approach is to expand the recurrence to convert it to a summation and then use summation techniques. The third approach is to take advantage of already proven theorems when the recurrence is of a suitable form. In particular, typical divide-and-conquer algorithms such as Mergesort yield recurrences of a form that fits a pattern for which we have a ready solution.

21.8.1.1. Estimating Upper and Lower Bounds

The first approach to solving recurrences is to guess the answer and then attempt to prove it correct. If a correct upper or lower bound estimate is given, an easy induction proof will verify this fact. If the proof is successful, then try to tighten the bound. If the induction proof fails, then loosen the bound and try again. Once the upper and lower bounds match, you are finished. This is a useful technique when you are only looking for asymptotic complexities. When seeking a precise closed-form solution (i.e., you seek the constants for the expression), this method will probably be too much work.

21.8.1.2. Expanding Recurrences

Estimating bounds is effective if you only need an approximation to the answer. More precise techniques are required to find an exact solution. One approach is called expanding the recurrence. In this method, the smaller terms on the right side of the equation are in turn replaced by their definition. This is the expanding step. These terms are again expanded, and so on, until a full series with no recurrence results. This yields a summation, and techniques for solving summations can then be used.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

21.8.1.3. Divide-and-Conquer Recurrences

The third approach to solving recurrences is to take advantage of known theorems that provide the solution for classes of recurrences. Of particular practical use is a theorem that gives the answer for a class known as divide-and-conquer recurrences. These have the form

\[{\bf T}(n) = a{\bf T}(n/b) + cn^k; \quad {\bf T}(1) = c\]

where \(a\), \(b\), \(c\), and \(k\) are constants. In general, this recurrence describes a problem of size \(n\) divided into \(a\) subproblems of size \(n/b\), while \(cn^k\) is the amount of work necessary to combine the partial solutions. Mergesort is an example of a divide and conquer algorithm, and its recurrence fits this form. So does binary search. We use the method of expanding recurrences to derive the general solution for any divide and conquer recurrence, assuming that \(n = b^m\).

\[\begin{split}\begin{eqnarray*} {\bf T}(n) & = & a{\bf T}(n/b) + cn^k\\ & = & a(a{\bf T}(n/b^2) + c(n/b)^k) + cn^k\\ & = & a(a[a{\bf T}(n/b^3) + c(n/b^2)^k] + c(n/b)^k) + cn^k\\ & = & a^m{\bf T}(1) + a^{m-1}c(n/b^{m-1})^k + \cdots + ac(n/b)^k + cn^k\\ & = & a^mc + a^{m-1}c(n/b^{m-1})^k + \cdots + ac(n/b)^k + cn^k\\ & = & c\sum_{i=0}^{m} a^{m-i} b^{ik}\\ & = &ca^m\sum_{i=0}^{m} (b^k/a)^i. \end{eqnarray*}\end{split}\]

Here is a more visual presentation of this same derivation.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

So, we are left with this result:

\[{\bf T}(n) = ca^m\sum_{i=0}^{m} (b^k/a)^i.\]

At this point, it is useful to note that

\[\begin{eqnarray} \label{ThmEquiv} a^m = a^{\log_bn} = n^{\log_ba}. \end{eqnarray}\]

This gives us

\[{\bf T}(n) = c n^{\log_ba} \sum_{i=0}^{m} (b^k/a)^i.\]

The summation part of this equation is a geometric series whose sum depends on the ratio \(r = b^k/a\). There are three cases.

  1. \(r<1\). From Equation (4) of Module summation,

    \[\sum_{i=0}^{m} r^i < 1/(1-r),\ {\rm a~constant.}\]

    Thus,

    \[{\bf T}(n) = \Theta(a^m) = \Theta(n^{log_ba}).\]
  2. \(r=1\). Because \(r = b^k/a\), we know that \(a = b^k\). From the definition of logarithms it follows immediately that \(k = \log_b a\). Also note that since we defined \(n = b^m\), then \(m = \log_b n\). Thus,

    \[\sum_{i=0}^{m} r^i = m + 1 = \log_bn + 1.\]

    Because \(a^m = n^{\log_b a} = n^k\), we have

    \[{\bf T}(n) = \Theta(n^{\log_ba}\log_b n) = \Theta(n^k\log_b n).\]
  3. \(r>1\). From Equation (5) of Module summation,

    \[\sum_{i=0}^{m} r^i = \frac{r^{m+1} - 1}{r - 1} = \Theta(r^m).\]

    Thus,

    \[{\bf T}(n) = \Theta(a^mr^m) = \Theta(a^m(b^k/a)^m) = \Theta(b^{km}) = \Theta(n^k).\]

We can summarize the above derivation as the following theorem, sometimes referred to as the Master Theorem.

This theorem may be applied whenever appropriate, rather than re-deriving the solution for the recurrence.

21.8.1.4. Average-Case Analysis of Quicksort

In Module Quicksort, we determined that the average-case analysis of Quicksort had the following recurrence:

\[{\bf T}(n) = cn + \frac{1}{n}\sum_{k=0}^{n-1} [{\bf T}(k) + {\bf T}(n -1 - k)], \qquad {\bf T}(0) = {\bf T}(1) = c.\]

The \(cn\) term is an upper bound on the findpivot and partition steps. This equation comes from assuming that the partitioning element is equally likely to occur in any position \(k\). It can be simplified by observing that the two recurrence terms \({\bf T}(k)\) and \({\bf T}(n - 1 - k)\) are equivalent, because one simply counts up from \(T(0)\) to \(T(n-1)\) while the other counts down from \(T(n-1)\) to \(T(0)\). This yields

\[{\bf T}(n) = cn + \frac{2}{n}\sum_{k=0}^{n-1} {\bf T}(k).\]

This form is known as a recurrence with full history. The key to solving such a recurrence is to cancel out the summation terms. The shifting method for summations provides a way to do this. Multiply both sides by \(n\) and subtract the result from the formula for \(n{\bf T}(n+1)\):

\[\begin{split}\begin{eqnarray*} n{\bf T}(n) & = & cn^2 + 2 \sum_{k=1}^{n-1} {\bf T}(k)\\ (n+1){\bf T}(n+1) & = & c(n+1)^2 + 2 \sum_{k=1}^{n} {\bf T}(k). \end{eqnarray*}\end{split}\]

Subtracting \(n{\bf T}(n)\) from both sides yields:

\[\begin{split}\begin{eqnarray*} (n+1){\bf T}(n+1) - n{\bf T}(n) & = & c(n+1)^2 - cn^2 + 2{\bf T}(n)\\ (n+1){\bf T}(n+1) - n{\bf T}(n) & = & c(2n+1) + 2{\bf T}(n)\\ (n+1){\bf T}(n+1) & = & c(2n+1) + (n+2){\bf T}(n)\\ {\bf T}(n+1) & = & \frac{c(2n+1)}{n+1} + \frac{n+2}{n+1}{\bf T}(n). \end{eqnarray*}\end{split}\]

At this point, we have eliminated the summation and can now use our normal methods for solving recurrences to get a closed-form solution. Note that \(\frac{c(2n+1)}{n+1} < 2c\), so we can simplify the result. Expanding the recurrence, we get

\[\begin{split}\begin{eqnarray*} {\bf T}(n+1) & \leq & 2c + \frac{n+2}{n+1} {\bf T}(n)\\ & = & 2c + \frac{n+2}{n+1}\left (2c + \frac{n+1}{n}{\bf T}(n-1)\right )\\ & = & 2c + \frac{n+2}{n+1}\left (2c + \frac{n+1}{n}\left (2c + \frac{n}{n-1}{\bf T}(n-2)\right )\right )\\ & = & 2c + \frac{n+2}{n+1}\left (2c + \cdots + \frac{4}{3}(2c + \frac{3}{2}{\bf T}(1))\right )\\ & = & 2c\left (1 + \frac{n+2}{n+1} + \frac{n+2}{n+1}\frac{n+1}{n} + \cdots + \frac{n+2}{n+1}\frac{n+1}{n}\cdots\frac{3}{2}\right )\\ & = & 2c\left (1 + (n+2)\left (\frac{1}{n+1} + \frac{1}{n} + \cdots + \frac{1}{2}\right )\right )\\ & = & 2c + 2c(n+2)\left ({\cal H}_{n+1} - 1\right )\\ \end{eqnarray*}\end{split}\]

for \({\cal H}_{n+1}\), the Harmonic Series. From Equation (10) of Module summation, \({\cal H}_{n+1} = \Theta(\log n)\), so the final solution is \(\Theta(n \log n)\).

   «  21.7. Summation Techniques   ::   Contents   ::   22.1. Chapter Introduction: Search  »

Close Window