GATE CSE 2026 Session 2 Q25: Recurrences that solve to Θ(n)

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity $\Theta(n)$ ?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, B (official GATE 2026 final answer key)

Concept used: Solve each recurrence by unrolling or the Master theorem.

First step: Unroll the subtractive ones as sums; apply the Master theorem with $a = 2$ , $b = 2$ to the others.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key