PA of Algorithms Q49

0. Consider the following recurrence
T(n) = 2T([√n]) + 1,T(1) = 1
Which one of the following is true?

Answer
Comment
Array

Option : B
Explanation :
T(n) = 2T(√n) + 1
Put n = 2^k
T(2^k) = 2T(n^k/2) + 1
replace T(2^k) by S(k)
S(k) = 2 S(k/2) + 1
Apply masters
K^log₂² ⇒ k > 1
So Θ(k)
Now we know n = 2^k, k = log₂(n)
then Θ(logn)

Forgot your password?

I agree with the Terms.