Consider the following recurrence relations: For all 𝑛>1, 𝑇1(𝑛) = 4𝑇1(𝑛 /…

GATE Β· 2026 Β· CS Β· Set 1 Β· Computer Science & IT

Consider the following recurrence relations:

For all 𝑛>1,

𝑇1(𝑛) = 4𝑇1(𝑛 / 2) + 𝑇2(𝑛)

𝑇2(𝑛) = 5𝑇2(𝑛 / 4) + Θ(log2𝑛)

Assume that for all 𝑛≀ 1,𝑇1(𝑛) =1 and 𝑇2(𝑛) = 1.

Which one of the following options is correct?

  1. A.

    𝑇1(𝑛)=Θ(𝑛2)

  2. B.

    𝑇1(𝑛)=Θ(𝑛2log2𝑛)

  3. C.

    𝑇1(𝑛)=Θ(𝑛log45)

  4. D.

    𝑇1(𝑛)=Θ(𝑛log45 log2𝑛)

Attempted by 188 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…