GATE CS 2007 Q45 — Asymptotic Worst Case Time and Space Complexity

To find the time complexity of the recursive function, let us write its recurrence relation. Let $T(n)$ represent the number of steps (or time complexity) taken by DoSomething(n).

For $n > 2$, the function makes one recursive call with the argument $\lfloor\sqrt{n}\rfloor$ and performs a constant amount of work, $\Theta(1)$, for the addition and comparison operations.

Thus, the recurrence relation is: $$T(n) = T(\sqrt{n}) + \Theta(1)$$ with the base case $T(n) = \Theta(1)$ for $n \le 2$.

We can solve this recurrence using the change of variables method:

1. Let $n = 2^m$, which implies $m = \log_2 n$.
2. Substituting this into the recurrence: $$T(2^m) = T\left(2^{m/2}\right) + \Theta(1)$$
3. Let $S(m) = T(2^m)$. The recurrence becomes: $$S(m) = S\left(\frac{m}{2}\right) + \Theta(1)$$

Applying Case 2 of the Master's Theorem to $S(m)$: $$S(m) = \Theta(\log_2 m)$$

Substituting back $m = \log_2 n$, we get: $$T(n) = \Theta(\log_2 \log_2 n)$$

Therefore, the time complexity of the function is $\Theta(\log_2 \log_2 n)$.