RECURRENCES

Consider the equation

$$T(n) = n \cdot T(n-1)$$

together with the ``stopping'' (or boundary) condition $T(0)=1$. Notice that this equation has the unknown function $T$ on both sides, so that it does not express a formula for computing $T$ directly, at least not in the usual sense. However, it does allow us to compute $T(n)$ in stages, first by reducing $T(n)$ to $n T(n-1)$ and then by substituting $n-1$ for $n$ in the same equation $T(n-1)$ becomes $(n-1)T(n-2)$ and so on:

$$T(n) = n T(n-1) = n(n-1)T(n-2) = n(n-1)(n-2)T(n-3) = \ldots = n(n-1)\ldots (n-k+1)T(n-k)$$

Here $k$ is the number of times we have used the equation to ``reduce'' the value of $n$. Let's keep this up until we reach the stopping condition, i.e., until $n-k=0$, or $k=n$. Then we get

$$T(n) = n(n-1) \ldots (n-n+1) T(0) = n! \times 1 = n!$$

That is, $T(n) = n!$, so T is the factorial function, and we have ``solved'' the ``recurrence equation'' above. The method we used is called ``iteration'' and it is quite general and powerful.

Here is another example, with boundary condition $S(1) = 3$:

$$S(n) = 2S(n/2) + n$$

$$S(n) = 2[2S(n/2^2) + n/2] + n$$

$$S(n) = 2[2[2S(n/2^3) + n/2^2] + n/2] + n$$

$$S(n) = 2^kS(n/2^k) + \sum_{i=0}^{k-1} 2^i n/2^i$$

If we keep this up until $2^k=n$ (to reach the boundary condition) then we get

$$S(n) = n S(1) + \sum_{i=0}^{k-1} 2^i n/2^i = 3n + n \sum_{i=0}^{k-1}1$$

$$S(n) = 3n + kn = 3n+ n \lg n = n \lg n + 3n$$

Thus we have solved this recurrence as well, using the same method.

In fact, this very method can be used to prove the ``Master Theorem'' which gives a formula for solutions to many (but not all) recurrences. Consult the Notes on this Theorem to learn how it works.

Using either the iteration method directly, or using the Master Theorem (in a special way), one can solve the Merge Sort runtime recurrence:

$$T(n) = 2T(n/2) + n - 1$$

to get

$$T(n) = n \lg n - n + 1$$

Thus Merge Sort has a runtime much better than (the worst-case or average case) for Insertion Sort.