Recurrence relation in DAA
Recurrence relation in DAA
The model that uses mathematical concepts to calculate the time complexity of an algorithm is known as the recurrence relational model.
A recursive relation, T(n), is a recursive function of integer n. Every recursive function consists of both recursive and base cases.
The section of the definition that does not contain T is called a base case of the recurrence relation, and the portion that contains T is called recursive or recursive relation.
Recurrence relations are very useful in calculating the running time complexities of recursive algorithms.
Example:
A Fibonacci sequence is defined by the recurrence relation - Fn = F(n-1) + F(n-2)
with initial conditions f1=1 and f2 = 1.
Example: Write the recurrence relation for the following method.
void f(int n) {
if (n > 0) {
cout << n;
f(n-1);
}
}
The base case is reached when n == 0. The method performs one comparison. Thus, the number of operations when n==0, T(0), is some constant a.
When n > 0, the method performs two basic operations and then calls itself, using ONE recursive call, with a parameter n - 1.
Therefore the recurrence relation is:
T(0) = a where a is constant
T(n) = b + T(n-1) where b is constant, n > 0
Solving recurrence relation
The following are the ways to solve a recurrence relation :
- Recursion Tree method
- Substitution method
- Master method
SUBSTITUTION METHOD
In the substitution method, we make a guess for the solution, and then we use mathematical induction to prove the guessed answer is right or wrong.
For example, Let us take the recurrence T(n) = 2T(n/2) + n
We guess the solution as T(n) = O(nLogn). Now we use induction
to prove our guess.
We need to prove that T(n) <= cnLogn. We can assume that it is true
for values smaller than n.
T(n) = 2T(n/2) + n
<= 2cn/2Log(n/2) + n
= cnLogn - cnLog2 + n
= cnLogn - cn + n
<= cnLogn
RECURRENCE TREE METHOD
In the recurrence tree method, a recurrence tree is drawn and calculates the time taken by every level of a tree. After analyzing each level, we sum up the work done at all levels. In order to draw a recurrence tree, start from the given recurrences and keep drawing till we find a pattern among all the levels. The pattern follows arithmetic or geometric series.
For example, consider the recurrence relation.
T(n) = T(n/4) + T(n/2) + cn2
cn2
/ \
T(n/4) T(n/2)
If we further break down the branches T(n/4) and T(n/2),
We get the following recursion tree:
cn2
/ \
c(n2)/16 c(n2)/4
/ \ / \
T(n/16) T(n/8) T(n/8) T(n/4)
Breaking down the tree further gives us the following result
cn2
/ \
c(n2)/16 c(n2)/4
/ \ / \
c(n2)/256 c(n2)/64 c(n2)/64 c(n2)/16
/ \ / \ / \ / \
To know the value of T(n), we need to calculate the sum of tree nodes level by level. The following series - T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + .... is obtained
on analyzing the end levels of the tree.
The above series is a geometric progression with a ratio of 5/16. We can sum the infinite series by calculating an upper bound.
We get the sum as (n2)/(1 - 5/16), which is having a time complexity of O(n2).
MASTER METHOD
We can get an immediate solution using the master method. The master method only works on the recurrence relations that can be transformed into the following relation:
T(n) = aT(n/b) + f(n) Here, a >= 1 and b > 1
There are following three cases:
1. If f(n) = ?(nc)
if c < Logba then T(n) = ?(Logban)
2. If f(n) = ?(nc)
if c = Logba then T(n) = ?(ncLog n)
3.If f(n) = ?(nc)
if c > Logba then T(n) = ?(f(n))
How does this work?
The master method is basically the derivation of the recurrence tree method. After drawing the recurrence tree of recurrence relation, T(n) = aT(n/b) + f(n),
we can observe that the task done at root is f(n) and task done at all leaves is ?(nc) where c is Logba. And the height of the recurrence tree is Logbn.
For example,
Merge sort - T(n) = 2T(n/2) + ?(n). The relation falls in 2 as c is 1 and Logba ] is also 1. So the solution is ?(n Logn)
Binary search: T(n) = T(n/2) + ?(1). This relation falls in 2 as c is 0 and Logba is also 0. So the solution is ?(Logn).