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) | t_{n} = t_{n-1} + 1 |
(selection sort) | t_{n} = t_{n-1} + n |
(binary search) | t_{n} = t_{n/2} + 1 |
(mergesort) | t_{n} = 2t_{n/2} + n |
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 } |
If the characteristic polynomial for t_{n} is the product of terms (E-a_{i})^{ei}, then t_{n} must be the sum of the form a_{i}^{n}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^{n}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_{1}=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_{2} n, and the recurrence for mergesort becomes s_{u} = 2s_{u-1} + 2^{u}, with characteristic polynomial (E-2)^{2} and solution s_{u} = 2^{u} (pu+q), or t_{n} = n(q + p log_{2} n). Thus t_{n} is Θ(n log n) as expected. Note that if t_{1}=0, then by the recurrence t_{2} = 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_{2} 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.