The GATE Grind

GATE 2026 CS (CS2) – Question 25

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple select

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

  1. $T(n)=T(n-1)+1$, $T(1)=1$
  2. $T(n)=2T(n/2)+1$, $T(1)=1$
  3. $T(n)=2T(n/2)+n$, $T(1)=1$
  4. $T(n)=T(n-1)+n$, $T(1)=1$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $T(n)=T(n-1)+1$, $T(1)=1$; (B) $T(n)=2T(n/2)+1$, $T(1)=1$

Explanation

For (A), repeated substitution gives $T(n)=T(n-1)+1=\Theta(n)$. For (B), the Master Theorem gives $T(n)=2T(n/2)+1=\Theta(n)$. For (C), $T(n)=2T(n/2)+n=\Theta(n\log n)$. For (D), summing the added terms gives $\Theta(n^2)$. Therefore, the recurrences with time complexity $\Theta(n)$ are (A) and (B).