Software-Engineering
December 9, 2023Software-Engineering
December 9, 2023Question 14108 – NIC-NIELIT STA 2020
What is the time complexity of the following recursive function?
int CompuFun (int n)
{
if(n<=2)
return
else
return (CompuFun (floor(sqrt(n)))+n);
}
Correct Answer: D
Question 43 Explanation:
Recurrence relation should be T(n)=T(n^1/2)+1 where n>2.
Here only (√(n)) is in the recursion call parameter. (+n) is just addition and it is a dependent value on recursion. So, we will only consider the recursion part for the recurrence relation.
It is ComputeFun(sqrt(n)).
We are only returning ComputeFun(√n)+n.
(+n) is not in a recursion call.
So recursive equation is,
T(n) = T(√n) + c
Here only (√(n)) is in the recursion call parameter. (+n) is just addition and it is a dependent value on recursion. So, we will only consider the recursion part for the recurrence relation.
It is ComputeFun(sqrt(n)).
We are only returning ComputeFun(√n)+n.
(+n) is not in a recursion call.
So recursive equation is,
T(n) = T(√n) + c
Now apply Master’s theorem,
a=1, b=2, k=0, p=0
a = bk, so Case-2 will be applied, and p>-1, so
θ(n)
θ(logn)
θ(nlogn)
θ(loglogn)