PA of Algorithms Q51

0. What is the time complexity of the following recursive function:

int DoSomething (int n)
{
if (n < = 2)
return 1;
else
return DoSomething (floor (sqrt (n)))+n;
}

Answer
Comment
Array

Option : D
Explanation :
The given function is recursive so the equivalent recursion equation is

All the level sums are equal to n. The problem size at level k of the recursion tree is n^{2– k} and we stop recursing when this value is a constant.
Setting n^2–k = 2 and solving for k gives us
2^{– k}log₂n = 1
2^k = log₂n
k = log₂ log₂n
So T(n) = θ(log₂ log₂n)

Forgot your password?

I agree with the Terms.