Introduction to the Concept
 Recurrence Relations are a recursive definitions of a mathematical functions or sequences. for example:
g(n) = g(n1) + 2n – 1
g(0) = 0
 this defines function f(n) = n^2, and the recurrence relation:
f(n) = f(n1) + f(n2)
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
 int Power(int x , int y )
 {
 if(y == 0)
 return 1;
 if(y == 1)
 return x;
 else
 return x*Power(x,y1);
 }

Notes(1):
 The size reduces from (n) to (n1) 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(n1) = T(n−2) + 2
 T(n) = [ T(n−2) +2 ] + 2 //by substitution
 T(n2) = 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(nk) ــــ to T(1) by setting (n−k = 1) , then
 T(n) = T(1) + 2(n−1)
 T(n) = 2n−1
 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
 int Power(int x , int y )
 {
 if(y == 0)
 return 1;
 if(y == 1)
 return x;
 elseif(y % 2 == 0)
 return Power(x*x,y/2);
 else
 return x*Power(x*x,y/2);
 }
 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:
 Data Structures and Algorithm Analysis in C++, Mark Allen .
 Tutorial for Recurrence Relations.
Advertisements
Nice topic Anas!
Keep it up man!
waiting your next post …
Also check this link: http://www.cs.usfca.edu/~brooks/S04classes/cs245/lectures/lecture4.pdf
Thanks, Dear Amr…