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