Consider the following recurrence relation: \(T(n) = \begin{cases} \sqrt{n}…

GATE · 2024 · CS · Set 1 · Computer Science & IT

Consider the following recurrence relation:

T(n)={n⋅T(n)+nfor n≥11for n=1T(n) = \begin{cases} \sqrt{n} \cdot T(\sqrt{n}) + n & \text{for } n \geq 1 \\ 1 & \text{for } n = 1 \end{cases}

Which one of the following options is CORRECT?

  1. A.

    𝑇(𝑛) = Θ(𝑛 log log 𝑛)

  2. B.

    𝑇(𝑛) = Θ(𝑛 log 𝑛)

  3. C.

    T(n)=Θ(n2log⁡n)T(n) = \Theta(n^2 \log n)

  4. D.

    T(n)=Θ(n2log⁡log⁡n)T(n) = \Theta(n^2 \log \log n)

Attempted by 108 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…