Consider the following recurrence relation. \(T\left ( n \right…

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

Consider the following recurrence relation.

T(n)={T(n∕2)+T(2n∕5)+7nif  n>01if  n=0T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.

Which one of the following options is correct?

  1. A.

    T(n)=Θ(n5/2)T(n)=\Theta (n^{5/2})

  2. B.

    T(n)=Θ(nlog⁡n)T(n)=\Theta (n\log n)

  3. C.

    T(n)=Θ(n)T(n)=\Theta (n)

  4. D.

    T(n)=Θ((log⁡n)5/2)T(n)=\Theta ((\log n)^{5/2})

Attempted by 112 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…