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.
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.
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.
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\).
\(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,
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)\):
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)\).