Consider the recurrence T(n) = 2T(⌊√n⌋) + 1, with T(1) = T(2) = 1. For…
ISRO Scientist/Engineer SC 2016Modified — slightly modified from the official paper; see the solution
Consider the recurrence T(n) = 2T(⌊√n⌋) + 1, with T(1) = T(2) = 1. For integers n ≥ 3, which choice gives the tightest asymptotic upper bound for T(n)?
- A.
T(n) = O(log log n)
- B.
T(n) = O(log n)
- C.
T(n) = O(√n)
- D.
T(n) = O(n)
Attempted by 399 students.
Sign up free to check your answer
Sign up freeLoading lesson…

