Question

Which of the following can be recurrence relation(s) corresponding to an algorithm
with time complexity Θ(𝑛)?

• A. 𝑇(𝑛) = 𝑇(𝑛−1) + 1, 𝑇(1) = 1
• B. \(T(n)=2T(n/2)+1,\quad T(1)=1\)
• C. \(T(n)=2T(n/2)+n,\quad T(1)=1\)
• D. 𝑇(𝑛) = 𝑇(𝑛−1) + 𝑛, 𝑇(1) = 1

Hint:

Solve each recurrence using unrolling or the Master theorem; only recurrences whose total work sums to a linear function of n qualify as Theta(n).

Answer 1

The Correct Option is A, B

Step 1: Solve each recurrence and find its Theta complexity.
Option A: \(T(n) = T(n-1) + 1\). Unrolling gives \(T(n) = T(1) + (n-1) = \Theta(n)\). This matches Theta(n).
Option B: \(T(n) = 2T(n/2) + 1\). By the Master theorem with \(a=2, b=2, f(n)=1\): \(\log_b a = 1\), and since \(f(n) = O(n^{\log_b a - \epsilon})\) for some \(\epsilon > 0\), Case 1 applies, so \(T(n) = \Theta(n^{\log_b a}) = \Theta(n)\). This matches Theta(n).
Option C: \(T(n) = 2T(n/2) + n\). Here \(f(n) = n = \Theta(n^{\log_b a})\), Case 2 applies, so \(T(n) = \Theta(n \log n)\), not Theta(n).
Option D: \(T(n) = T(n-1) + n\). Unrolling gives \(T(n) = n + (n-1) + \dots + 1 = \Theta(n^2)\), not Theta(n).
Step 2: Only options A and B produce Theta(n) complexity.
Final Answer: Options A and B