Concept Of Recurrence Relations

Introduction to the Concept

g(n) = g(n-1) + 2n – 1
g(0) = 0
    • this defines function f(n) = n^2, and the recurrence relation:
f(n) = f(n-1) + f(n-2)
f(1) = 1
f(0) = 0

Solving a Recurrence Relation

  • There are many techniques to solve Recurrence Relations, the main techniques are Iteration Method (also known as expansion or unfolding method) and the Master Theorem method. 
  • In this post we’ll talk about Iteration Method
Simple Recursive Power Algorithm 
Simple Power Function
  1. int Power(int x , int y )
  2. {
  3.     if(y == 0)
  4.         return 1;
  5.     if(y == 1)
  6.         return x;
  7.     else
  8.         return x*Power(x,y-1);
  9. }
  • Notes(1):

    • The size reduces from (n) to (n-1) at every step.
    • Two arithmetic operations are involved (Multiplication/Subtraction).
    • Total number of operations ــــ needed to execute the function for any given(n) ــــ can be expressed as sum of two operations. 
    • When (n = 1),  it needs one operation to execute the function.
    • Then, Recurrence Relation will be as follows:
      • T(n) = T(n−1) + 2
      • T(1) = 1
    • We’ll try to reduce the RHS till we get T(1)
      • T(n-1) = T(n−2) + 2
      • T(n) = [ T(n−2) +2 ] + 2        //by substitution 
      • T(n-2) = T(n−3) + 2
      • T(n) = [ T(n−3) +2 ]+2+2   //by substitution 
    • Then the general formula  will be:
      • T(n) = T(n−k)  + 2(k).
    • So, we can reduce RHS ــــ T(n-k) ــــ to T(1) by setting (n−k = 1) , then 
      • T(n) = T(1) + 2(n1)
      • T(n) = 2n1
    • Finally, we get the RHS without any terms involving functions like “T(..)”, Yeaaaah!! The Recurrence Relation has been solved.
      • This Equation is linear in (n), so Complexity of this algorithm  is o(n). 
OK! Lets talk about efficient Recursive Power algorithm 
Efficient Power Function
  1. int Power(int x , int y )
  2. {
  3.     if(y == 0)
  4.         return 1;
  5.     if(y == 1)
  6.         return x;
  7.     elseif(y % 2 == 0)
  8.         return Power(x*x,y/2);
  9.     else
  10.         return x*Power(x*x,y/2);
  11. }
  • Notes(2):
    • every step reduces to half size.
    • when the power is and odd number, and additional multiplication involved to increase time complexity as worst case .
    • total number of operations are T(n) will reduces number of operation (n/2) then, T(n/2) has three additional arithmetic operations (2 Multiplication, 1 Division).
    • Recurrence Relation will be as follows:
      • T(n)  = T(n/2) + 3
      • T(1) = 1
    • as the previous example we’ll try to reduce the RHS till we get T(1)
      • T(n/2) = T(n/4) + 3
      • T(n) = [T(n/4)+3] + 3  //by substitution 
    • So, let’s have a deeper look:

      • T(n) = T(n/2) +3
      • T(n) = [T(n/4)+3]+3 
      • T(n) = [T(n/8)+3] + 3(2)
      • T(n) = T(n/8) + 3(3)
    • Got it ?!!, the general formula  will be:

      • T(n) = T(n/2ˆk)  + 3k
    • So, we can reduce the RHS to T(1) by setting (2ˆk = n) 
      • T(n) = T(1) + 3 log(n)
    • Thus, we can say that the algorithm runs in a logarithmic time
References:
Advertisements

2 thoughts on “Concept Of Recurrence Relations

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s