Recurrence relations in the analysis of algorithms

Let t_n 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 t_n.

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 t_n 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 t_n is the product of terms (E-a_i)^e_i, then t_n must be the sum of the form a_iⁿr_i, and conversely, where r_i is any polynomial of degree e_i-1. For example, for selection sort we have t_n = 1ⁿr(n), where r is a polynomial of degree 3-1. Thus t_n is quadratic in n, as expected. In general, an exact solution may be found if enough initial conditions (e.g., t₁=0) are known.

The last two examples require a domain transformation. For example, if we let n=2^u and t_n = s_u, then u = log₂ n, and the recurrence for mergesort becomes s_u = 2s_u-1 + 2^u, with characteristic polynomial (E-2)² and solution s_u = 2^u (pu+q), or t_n = n(q + p log₂ n). Thus t_n is Θ(n log n) as expected. Note that if t₁=0, then by the recurrence t₂ = 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 t_n = n log₂ 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 t_n correspond to annihilators of such a sequence -- that is, operators that convert the sequence into the sequence whose terms are all 0.