Consider the recurrence function \(T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2…

GATE · 2017 · CS · Set 2 · Computer Science & IT

Consider the recurrence function

T(n)={2T(n)+1,n>22,0<n≤2T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}

Then T(n)T(n) in terms of Θ\Theta notation is

  1. A.

    Θ(log⁡log⁡n)\Theta(\log \log n)

  2. B.

    Θ(log⁡n)\Theta( \log n)

  3. C.

    Θ(n)\Theta (\sqrt{n})

  4. D.

    Θ(n)\Theta(n)

Attempted by 149 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…