GATE CS 2006 Q51 — Asymptotic Worst Case Time and Space Complexity

To solve the recurrence relation $T(n) = 2T(\sqrt{n}) + 1$, we can use the change of variables method.

Let $n = 2^m$, which implies $m = \log_2 n$.

Substituting this into the recurrence:

Now, let $S(m) = T(2^m)$. The recurrence relation can be rewritten as:

We can solve this new recurrence using the Master Theorem for divide-and-conquer recurrences of the form $S(m) = aS(m/b) + f(m)$:

• Here, $a = 2$, $b = 2$, and $f(m) = 1$.
• Compare $f(m)$ with $m^{\log_b a} = m^{\log_2 2} = m^1 = m$.
• Since $f(m) = O(m^{1-\epsilon})$ for any $\epsilon > 0$, we fall into Case 1 of the Master Theorem.

Therefore, the solution for $S(m)$ is:

Substituting back $m = \log_2 n$:

Thus, the correct option is B.