ADS

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)
Recurrences And Their Solution Methods

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:
Recurrences And Their Solution Methods

Second Example
Recurrences And Their Solution Methods

Recurrences And Their Solution Methods

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


Post a Comment

0 Comments