Created on: July 9, 2009

Website Address: https://library.curriki.org/oer/Recurrence-Relations-37924

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.

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)***

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)***

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.