RECURRENCE RELATIONS

When an algorithm contains a recursive call to itself, its running time can often be described by a recurrence. A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs.

The different methods of solving a recurrence relation are describe below.

1. METHOD OF SUBSTITUTION

In the substitution method, we guess a bound and then use mathematical induction to prove our guess correct. The iteration method converts the recurrence into a summation and then relies on techniques for bounding summations to solve the recurrence. The master method provides bounds for recurrences of the form

• T(n) = aT(n/b) + f(n)*
Where a ? 1, b > 1, and f(n) is a given function; it requires memorization of three cases, but once you do that, determining asymptotic bounds for many simple recurrences is easy. The substitution method for solving recurrences involves guessing the form of the solution and then using mathematical induction to find the constants and show that the solution works. The name comes from the substitution of the guessed answer for the function when the inductive hypothesis is applied to smaller values. This method is powerful, but it obviously can be applied only in cases when it is easy to guess the form of the answer.
The substitution method can be used to establish either upper or lower bounds on a recurrence.

2. METHOD OF ITERATION

The method of iteration a recurrence doesn’t require us to guess the answer. But it may require more algebra than the substitution method. The idea is to expand (iterate) the recurrence and express it as a summation of terms dependent only on n and the initial conditions. Techniques for evaluating summations can then be used to provide bounds on the solution.
The iteration method usually leads to lots of algebra, and keeping everything straight can be a challenge. The key is to focus on two parameters: the number of times the recurrence needs to be iterated to reach the boundary condition, and the sum of the terms arising from each level of the iteration process.

3. MASTER METHOD

The master method provides a “cookbook” method for solving recurrences of the form

• T(n) = aT(n/b) + f(n)*
Where a ? 1 and b > 1 are constant and f(n) is an asymptotically positive function. The master method requires memorization of three cases, but then the solution of many recurrences can be determined quite easily, often without pencil and paper.
The recurrence (1) describes the running time of an algorithm that divides a problem of size n into a sub problems, each of size n/b. where a and b are positive constants. The sub-problems are solved recursively, each in time T(n/b). The cost of dividing the problem and combining the results of the sub problems is described by the function f(n). For example, the recurrence arising from the MERGE-SORT procedure has a=2, b=2, and f(n) = ?(n).

REFERENCE BOOK FOR RECURRENCE

THOMAS H. CORMEN, CHARLES E. LEISERSON and RONALD L RIVEST (1990): Introduction to Algorithms. The MIT Press.

Non-profit Tax ID # 203478467