Consider the following recurrence: T(n) = 2T(√n) + 1, with T(1) = 1. Which of…

The recurrence is:
T(n) = 2T(√n) + 1, with T(1) = 1.

This cannot be solved as T(n) = 2T(n/2) + 1 because the subproblem size is √n, not n/2.

Let n = 2^m. Then √n = 2^(m/2).
Define S(m) = T(2^m).

Now:
S(m) = 2S(m/2) + 1.

Using the Master Theorem on S(m), we have a = 2, b = 2, and f(m) = 1.
So S(m) = Θ(m).

Since m = log n, we get:
T(n) = Θ(log n).

Therefore, the correct option is T(n) = O(log n).