Consider the recurrence function $$T(n) = \begin{cases} 2T(\sqrt{n}) + 1, & n > 2 \\ 2, & 0 < n \le 2 \end{cases}$$ Then $T(n)$ in terms of $\Theta$ notation is

We are given the recurrence relation:

To solve this recurrence, change the variable: Let $n = 2^m \implies m = \log_2 n$.

Then $\sqrt{n} = n^{1/2} = 2^{m/2}$.

Substituting this into the recurrence:

Define a new function $S(m) = T(2^m)$:

Now, applying the Master Theorem for $S(m) = a S(m/b) + f(m)$:

• $a = 2$

• $b = 2$

• $f(m) = 1 = \Theta(m^0)$

• Critical exponent: $\log_b a = \log_2 2 = 1$

Since $f(m) = O(m^{1 - \epsilon})$ for $\epsilon = 1$, Case 1 of the Master Theorem applies:

Substitute back $m = \log_2 n$:

Therefore, the correct asymptotic bound is $\Theta(\log n)$, which corresponds to Option (B).