# 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