Recurrence relations in the analysis of algorithms

In the divide-and-conquer approach to algorithm design, a data structure of size n is processed by first processing one or more pieces of size k < n. The resulting algorithm is naturally expressed recursively, but may be converted to an iterative version without affecting the analysis.

Let tn stand for the worst-case time to execute a given algorithm with input of size n. Then for divide-and-conquer algorithms, there's usually a natural recurrence relation for tn.

Some examples for familiar algorithms:
(sequential search) tn = tn-1 + 1
(selection sort) tn = tn-1 + n
(binary search) tn = tn/2 + 1
(mergesort) tn = 2tn/2 + n
In each case, the final term represents the time required by the algorithm in addition to the time needed to process the pieces.

Given a recurrence relation, the possible values for tn may be found by first finding a characteristic polynomial. The characteristic polynomials for the first two examples above are respectively
(sequential search) (E-1)2
(selection sort) (E-1)3
Here we use E for the variable to be consistent with Smith[1989].

If the characteristic polynomial for tn is the product of terms (E-ai)ei, then tn must be the sum of the form ainri, and conversely, where ri is any polynomial of degree ei-1. For example, for selection sort we have tn = 1nr(n), where r is a polynomial of degree 3-1. Thus tn is quadratic in n, as expected. In general, an exact solution may be found if enough initial conditions (e.g., t1=0) are known.

The last two examples require a domain transformation. For example, if we let n=2u and tn = su, then u = log2 n, and the recurrence for mergesort becomes su = 2su-1 + 2u, with characteristic polynomial (E-2)2 and solution su = 2u (pu+q), or tn = n(q + p log2 n). Thus tn is Θ(n log n) as expected. Note that if t1=0, then by the recurrence t2 = 2*0+2 = 2. These two equations are enough to deterimine p and q; a little algebra shows that q=0 and p=1, so that tn = n log2 n exactly.

What happens when n is not a power of 2 in cases like the previous one will be discussed in class. Also to be discussed in class will be a method of finding characteristic polynomials. Briefly, the idea is that characteristic polynomials for sequences tn correspond to annihilators of such a sequence -- that is, operators that convert the sequence into the sequence whose terms are all 0.