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