3.18. Solving Recurrence Relations (optional) (WORK IN PROGRESS)¶
3.18.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
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.
3.18.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.
Example 3.19.1
Use the guessing technique to find the asymptotic bounds for Mergesort, whose running time is described by the equation
We begin by guessing that this recurrence has an upper bound in \(O(n^2)\). To be more precise, assume that
We prove this guess is correct by induction. In this proof, we assume that \(n\) is a power of two, to make the calculations easy. For the base case, \({\bf T}(2) = 1 \leq 2^2\). For the induction step, we need to show that \({\bf T}(n) \leq n^2\) implies that \({\bf T}(2n) \leq (2n)^2\) for \(n = 2^N, N \geq 1\). The induction hypothesis is
It follows that
which is what we wanted to prove. Thus, \({\bf T}(n)\) is in \(O(n^2)\).
Is \(O(n^2)\) a good estimate? In the next-to-last step we went from \(n^2 + 2n\) to the much larger \(4n^2\). This suggests that \(O(n^2)\) is a high estimate. If we guess something smaller, such as \({\bf T}(n) \leq cn\) for some constant \(c\), it should be clear that this cannot work because \(c 2 n = 2 c n\) and there is no room for the extra \(n\) cost to join the two pieces together. Thus, the true cost must be somewhere between \(cn\) and \(n^2\).
Let us now try \({\bf T}(n) \leq n \log n\). For the base case, the definition of the recurrence sets \({\bf T}(2) = 1 \leq (2 \cdot \log 2) = 2\). Assume (induction hypothesis) that \({\bf T}(n) \leq n \log n\). Then,
which is what we seek to prove. In similar fashion, we can prove that \({\bf T}(n)\) is in \(\Omega(n \log n)\). Thus, \({\bf T}(n)\) is also \(\Theta(n \log n)\).
Example 3.19.2
We know that the factorial function grows exponentially. How does it compare to \(2^n\)? To \(n^n\)? Do they all grow “equally fast” (in an asymptotic sense)? We can begin by looking at a few initial terms.
We can also look at these functions in terms of their recurrences.
At this point, our intuition should be telling us pretty clearly the relative growth rates of these three functions. But how do we prove formally which grows the fastest? And how do we decide if the differences are significant in an asymptotic sense, or just constant factor differences?
We can use logarithms to help us get an idea about the relative growth rates of these functions. Clearly, \(\log 2^n = n\). Equally clearly, \(\log n^n = n \log n\). We can easily see from this that \(2^n\) is \(o(n^n)\), that is, \(n^n\) grows asymptotically faster than \(2^n\).
How does \(n!\) fit into this? We can again take advantage of logarithms. Obviously \(n! \leq n^n\), so we know that \(\log n!\) is \(O(n \log n)\). But what about a lower bound for the factorial function? Consider the following.
Therefore
In other words, \(\log n!\) is in \(\Omega(n \log n)\). Thus, \(\log n! = \Theta(n \log n)\).
Note that this does not mean that \(n! = \Theta(n^n)\). Because \(\log n^2 = 2 \log n\), it follows that \(\log n = \Theta(\log n^2)\) but \(n \neq \Theta(n^2)\). The log function often works as a “flattener” when dealing with asymptotics. That is, whenever \(\log f(n)\) is in \(O(\log g(n))\) we know that \(f(n)\) is in \(O(g(n))\). But knowing that \(\log f(n) = \Theta(\log g(n))\) does not necessarily mean that \(f(n) = \Theta(g(n))\).
Example 3.19.3
What is the growth rate of the Fibonacci sequence? We define the Fibonacci sequence as \(f(n) = f(n-1) + f(n-2)\) for \(n \geq 2\); \(f(0) = f(1) = 1\).
In this case it is useful to compare the ratio of \(f(n)\) to \(f(n-1)\). The following table shows the first few values.
If we continue for more terms, the ratio appears to converge on a value slightly greater then 1.618. Assuming \(f(n)/f(n-1)\) really does converge to a fixed value as \(n\) grows, we can determine what that value must be.
for some value \(x\). This follows from the fact that \(f(n) = f(n-1) + f(n-2)\). We divide by \(f(n-2)\) to make the second term go away, and we also get something useful in the first term. Remember that the goal of such manipulations is to give us an equation that relates \(f(n)\) to something without recursive calls.
For large \(n\), we also observe that:
as \(n\) gets big. This comes from multiplying \(f(n)/f(n-2)\) by \(f(n-1)/f(n-1)\) and rearranging.
If \(x\) exists, then \(x^2 - x - 1 \rightarrow 0\). Using the quadratic equation, the only solution greater than one is
This expression also has the name \(\phi\). What does this say about the growth rate of the Fibonacci sequence? It is exponential, with \(f(n) = \Theta(\phi^n)\). More precisely, \(f(n)\) converges to
3.18.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.
Example 3.19.4
Our next example models the cost of the algorithm to build a heap. You should recall that to build a heap, we first heapify the two subheaps, then push down the root to its proper position. The cost is:
Let us find a closed form solution for this recurrence. We can expand the recurrence a few times to see that
We can deduce from this expansion that this recurrence is equivalent to following summation and its derivation:
3.18.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
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\).
Here is a more visual presentation of this same derivation.
So, we are left with this result:
At this point, it is useful to note that
This gives us
The summation part of this equation is a geometric series whose sum depends on the ratio \(r = b^k/a\). There are three cases.
\(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}).\]\(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).\]\(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.
Theorem 3.19.1
The Master Theorem: For any recurrence relation of the form \({\bf T}(n) = a{\bf T}(n/b) + cn^k, {\bf T}(1) = c\), the following relationships hold.
This theorem may be applied whenever appropriate, rather than re-deriving the solution for the recurrence.
Example 3.19.5
Apply the Master Theorem to solve
Because \(a=3\), \(b=5\), \(c=8\), and \(k=2\), we find that \(3<5^2\). Applying case (3) of the theorem, \({\bf T}(n) = \Theta(n^2)\).
Example 3.19.6
Use the Master Theorem to solve the recurrence relation for Mergesort:
Because \(a=2\), \(b=2\), \(c=1\), and \(k=1\), we find that \(2 = 2^1\). Applying case (2) of the theorem, \({\bf T}(n) = \Theta(n \log n)\).
3.18.1.4. Average-Case Analysis of Quicksort¶
In Module Quicksort, we determined that the average-case analysis of Quicksort had the following recurrence:
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
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)\):
Subtracting \(n{\bf T}(n)\) from both sides yields:
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
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)\).
