GATE CS 2026 Set 2 Q.25: Asymptotic Analysis and Time/Space Complexity

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

$T(n) = T(n - 1) + 1, \quad T(1) = 1$

$T(n) = 2T\left(\frac{n}{2}\right) + 1, \quad T(1) = 1$

$T(n) = 2T\left(\frac{n}{2}\right) + n, \quad T(1) = 1$

$T(n) = T(n - 1) + n, \quad T(1) = 1$

Official answer and solution

Solution

Solve each recurrence relation using telescoping sums or the Master Theorem.

Evaluating each option:

(A) $T(n) = T(n-1) + 1$ with $T(1) = 1$ unrolls to $T(n) = n = \Theta(n)$ .
(B) $T(n) = 2T(n/2) + 1$ : by the Master Theorem ( $a=2, b=2, n^{\log_b a} = n$ , $f(n) = 1 = O(n^{1-\epsilon})$ ), $T(n) = \Theta(n)$ .
(C) $T(n) = 2T(n/2) + n$ gives $T(n) = \Theta(n \log n)$ .
(D) $T(n) = T(n-1) + n$ gives $T(n) = \frac{n(n+1)}{2} = \Theta(n^2)$ .

Therefore, (A) and (B) have time complexity $\Theta(n)$ .

Final answer

Options (A), (B)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 25 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.