Lecture 4
Analysis of Time Complexity for
Recursive Algorithm
Definition of a Recursive Function
Any function which calls itself is called recursive. A
recursive method solves a problem by calling a copy
of itself to work on a smaller problem. This is called
the recursion step. The recursion step can result in
many more such recursive calls.
Why Recursion?
Recursion is a useful technique borrowed from
mathematics. Recursive code is generally shorter and
easier to write than iterative code. Generally, loops
are turned into recursive functions when they are
compiled or interpreted.
Analysis of Recursive Programs
A(n)
{
if(…)
return A(n/2)+A(n/2)
}
Example 1
void Test(int n)
{
if(n>0)
{
printf(“%d”,n);
Test(n-1)
}
}
Example 2
Void Test(int n)
{
if(n>0)
{
for(i=0; i<n; i++)
{
print(“%d”,n);
}
Test(n-1);
}
}
Example using Recursion Tree-Method
Void Test(int n)
{
if(n>0)
{
for(i=0; i<n; i++)
{
print(“%d”,n);
}
Test(n-1);
}
Exercise 3: using back sybstitution
Void Test(int n)
{
if(n>1)
{
for(i=0;i<n; i++)
{
statements;
}
Test(n/2);
Test(n/2);
}
Master Theorem
T(n)= 2T(n/2)+n
where a>=1,b>1,k>=0 and p is real number.
T(n)= 3T(n/2)+
a=3, b=2, k=2, p=0
=4
a<
3)a) T(n)= O(n)
T(n)= O(n) O()
T(n)= 4T(n/2)+
a=4, b=2, k=2,p=0
b.k = 4, a=
2)a) T(n)= O(. )
O(.logn)
T(n)=2T(n/2)+ n/logn
T(n)=2T(n/2)+n.
a=2,b=2,k=1,p=-1
=2 a=
2)b) T(n)= O(.loglogn)
T(n)= O(.loglogn)
T(n)= 0.5T(n/2)+1/n
Master Theorem is not applicable for this
equation.
T(n)= T(n/2)+logn
a= , b=2, k=0,p=1
a>bk T(n)= O() O()
T(n)= 2T(n/2)+
a=2,b=2, k=1/2,p=0
T(n)=2T(n/2)-nlogn
Problems: solve the following problems using
Master Theorem
1. T(n)= 3T(n/2)+
2. T(n)= 4T(n/2)+
3. T(n)= T(n/2)+
4. T(n)= 2nT(n/2)+
5. 16T(n/4) + n
6. T(n)=2T(n/2)+nlogn
7. T(n)=2T(n/2)+ n/logn
8. T(n)= 2T(n/4)+
9. T(n)= 0.5T(n/2)+1/n
Questions??
