A recurrence relation is an equation that recursively defines a sequence of values and each term of the sequence is defined as a function of the preceding terms.
Or
A recurrence relation is an equation that expresses elements of a sequence as a function of the preceding ones.
E.g.
1) n! = n (n-1)!
2) T(n)= T(n-1) + 1
There are 3 methods of obtaining the complexity:
1.Substitution method
2.Recursive tree method
3.Master’s Theorem method
1. Recursive Tree Method
Consider the following code:
So the recurrence relation can be written as:
T(n) = T(n-1) +1 n>0
= 1 n=0
Pass 3 to the function and draw the recursive tree:
Consider another example:
So the recurrence relation can be written as:
T(n) = T(n-1) +n n>0
= 1 n=0
Sum up:
T(n)= 0+1+2+……..+ (n-2)+ (n-1)+ n
= n(n+1)/2 It is an arithmetic progression representing the sum of the first n 𝑛 consecutive natural numbers, which evaluates to the formula n(n+1)/2
Therefore, T(n) is in O(n2)
Test(int n)
{
if (n>0)
{
for(i=1;i<n;i=i*2)
{
printf(“%d”, i);
}
Test(n-1);
}
}
Total time: T(n) = T(n-1) +2log n+2 or T(n) = T(n-1) +log n
T(n) = T(n-1) +log n n>0
= 1 n=0