Correct Answer - Option 2 : Θ (log n)
\(T\left( n \right) = 2\;T\left( {\sqrt n } \right) + 1\)
Put n= 2m, m = log2n
\(T\left( {{2^m}} \right) = 2T\left( {{2^{\frac{m}{2}}}} \right) + 1\)
\(Put\;T\left( {{2^m}} \right) = S\left( m \right)\)
\(S\left( m \right) = 2\;S\;\left( {\frac{m}{2}} \right) + 1\)
Now, calculate \({n^{log_b^a}}\)
\({m^{log_b^a}} = m\)
S (m) = m + 1
S(m) = m
Put the value of m
Therefore, T(n) in terms of Θ notation is Θ (logn).