Java Reference
In-Depth Information
14.2
Recurrence Relations
Recurrence relations are often used to model the cost of recursive functions. For
example, the standard Mergesort (Section 7.4) 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
T(n) = 2T(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 con-
sider 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 re-
quired. The second approach is to expand the recurrence to convert it to a summa-
tion 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 particu-
lar, typical divide and conquer algorithms such as Mergesort yield recurrences of a
form that fits a pattern for which we have a ready solution.
14.2.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.
Example14.5
Use the guessing technique to find the asymptotic bounds
for Mergesort, whose running time is described by the equation
T(n) = 2T(n=2) + n;
T(2) = 1:
We begin by guessing that this recurrence has an upper bound in O(n
2
). To
be more precise, assume that
T(n) n
2
:
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,
