GATE 2026 CS2 Q.25: solution and answer

Official answer: A, BSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

1. Option A: $T(n)=T(n-1)+1$, $T(1)=1$. Unrolling: $T(n)=T(n-1)+1=T(n-2)+2=\cdots =T(1)+(n-1)=n$. So $T(n)=\Theta (n)$ — qualifies.

2. Option B: $T(n)=2T(n/2)+1$. Master theorem with $a=2,b=2,f(n)=1$: $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n$. Since $f(n)=1=O(n^{1-\epsilon })$ for $\epsilon =1$, this is Case 1, so $T(n)=\Theta (n^{{\log }_{b}a})=\Theta (n)$ — qualifies.

3. Option C: $T(n)=2T(n/2)+n$. Master theorem with $a=2,b=2,f(n)=n$: $n^{{\log }_{b}a}=n$, and $f(n)=n=\Theta (n^{{\log }_{b}a})$, so this is Case 2, giving $T(n)=\Theta (n\log n)$ — this is not $\Theta (n)$, so it does not qualify.

4. Option D: $T(n)=T(n-1)+n$. Unrolling: $T(n)=T(n-1)+n=T(n-2)+(n-1)+n=\cdots =T(1)+(2+3+\cdots +n)=\Theta (n^2)$ (sum of an arithmetic series) — this is not $\Theta (n)$, so it does not qualify.

5. Only A and B evaluate to $\Theta (n)$; C is $\Theta (n\log n)$ and D is $\Theta (n^2)$.