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)?

  1. A.

    T(n) = O(log log n)

  2. B.

    T(n) = O(log n)

  3. C.

    T(n) = O(√n)

  4. D.

    T(n) = O(n)

Attempted by 399 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…