Introduction to the Concept
- Recurrence Relations are a recursive definitions of a mathematical functions or sequences. for example:
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
- 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(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
- 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