GATE CS 2017 Set 2 Q30 — Asymptotic Worst Case Time and Space Complexity

To solve the given recurrence relation:

We can use the change of variables method. Let $n = 2^k$, which implies $k = \log_2 n$.

Substituting this into the recurrence:

Let $S(k) = T(2^k)$. The recurrence relation becomes:

We can now apply the Master Theorem for divide-and-conquer recurrences of the form $S(k) = aS(k/b) + f(k)$:

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

Thus, the solution for $S(k)$ is:

Substituting back $k = \log_2 n$:

Therefore, the correct option is B.