Time complexity

Question

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;
}

1. $\theta(n^2)$
2. $\theta(n \log_2 n)$
3. $\theta(\log_2 n)$
4. $\theta(\log_2 \log_2 n)$

Answer 1

return $DoSomething(floor(sqrt(n)))$ + n;

=> Here '+ n' is not a function of input size n. It takes only constant time always.

So the time complexity becomes simply $T(n)$ = $T(\sqrt{n}) + c$

which you can solve either by substitution method or by Master's Theorem and can get the solution.

The solution for this relation is $\Theta (log (log n))$.

Hence, the answer is (D).

Comments

Why n is not a function here.

---

The function DoSomething ends by calculating the sqrt. The brackets end there. No matter what the value of n is, + n is executed only once here.

---

The function DoSomething ends by calculating the sqrt. The brackets end there. No matter what the value of n is, + n is executed only once here. Note that recursive function here is 'sqrt'.