# Recurrences And Their Solution Methods

## Recurrences

• Recursive algorithms are described by using recurrence relations.
• A recurrence is an inequality that describes a problem in terms of itself.
For Example:
Recursive algorithm for finding factorial
T(n)=1     when n =1
T(n)=T(n-1) + O(1)    when  n>1
Recursive algorithm for finding Nth Fibonacci number
T(1)=1     when n=1 T(2)=1     when n=2
T(n)=T(n-1) + T(n-2) +O(1)     when n>2
Recursive algorithm for binary search
T(1)=1     when n=1
T(n)=T(n/2) + O(1)    when n>1

Techniques for Solving Recurrences We’ll use four techniques:
1. Iteration method
2. Recursion Tree
3. Substitution
4. Master Method   – for divide & conquer
5. Characteristic Equation   – for linear

### Iteration method

Expand the relation so that summation independent on n is obtained.
Bound the summation e.g.
T(n)= 2T(n/2) +1  when n>1
T(n)= 1    when n=1
T(n) = 2T(n/2) +1
= 2 { 2T(n/4) + 1} +1
= 4T(n/4) + 2 + 1
= 4 { T(n/8) +1 } + 2 + 1
= 8 T(n/8) + 4 + 2 + 1
………………………
………………………
= 2^k T( n/2^k) + 2^(k-1) T(n/2^(k-1)) + ………………… + 4 + 2 + 1.
For simplicity assume:
n= 2^k
k=logn
T(n)= 2^k + 2^(k-1) + ……………………….. + 2^2 + 2^1 + 2^0
T(n)= (2^(k+1) -1)/ (2-1)
T(n)= 2^(k+1) -1
T(n)= 2.2^k -1
T(n)= 2n-1
T(n)= O(n)

### Substitution Method

Takes two steps:
• Guess the form of the solution, using unknown constants.
• Use induction to find the constants & verify the solution.

Completely dependent on making reasonable guesses
Consider the example:

Second Example

Changing Variables:
Sometimes a little algebraic manipulation can make a unknown recurrence similar to one we have seen
Consider the example