Gate2017 ss Q46
0. Consider the recurrence function
Then T(n) in terms of θ notation is
- Option : B
- Explanation : T(n) = 2T(√n) + 1
Put n = 2K
T(2K) = 2T(2K/2) + 1
T(2K) = δ(K)
By master's theorem
δ(K) = θ(K)
T(2K) = θ(K)
T(n) = θ(log n) ∵ 2K = n
