Consider the following recurrence: Which one of the following is true?

Recurrence: T(n) = 2 T(ceil(sqrt(n))) + 1, with T(1) = 1.

Key idea: repeatedly take square roots until the problem size becomes constant; count nodes at each level.

• Size at level i: n_i = n^{1/2^i} (after i square-root reductions).

• Number of nodes at level i: 2^i.

• Stop when n^{1/2^k} = Θ(1). Taking logs: (1/2^k)·log n = Θ(1) ⇒ 2^k = Θ(log n) ⇒ k = Θ(log log n).

• Total cost: sum_{i=0}^{k} 2^i · Θ(1) = Θ(2^k) = Θ(log n).

Conclusion: T(n) = Θ(log n). The choice stating Θ(log n) is the correct asymptotic.