Question

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

• A. \(T(n) = T(n-1) + 1, \quad T(1) = 1\)
• B. \(T(n) = 2T\left(\dfrac{n}{2}\right) + 1, \quad T(1) = 1\)
• C. \(T(n) = 2T\left(\dfrac{n}{2}\right) + n, \quad T(1) = 1\)
• D. \(T(n) = T(n-1) + n, \quad T(1) = 1\)

Hint:

Use the Master Theorem or expand each recurrence directly, then compare the resulting closed form against n, n log n, and n squared growth rates.

Answer 1

The Correct Option is A, B

Step 1: Understand what Theta(n) means.
A recurrence gives \(\Theta(n)\) growth if solving it produces a running time that is a constant multiple of \(n\), no more and no less. We check each option by expanding it directly or by applying the Master Theorem.

Step 2: Check option (A).
\[ T(n) = T(n-1) + 1, \quad T(1) = 1 \]
This recurrence adds \(1\) at every step going from \(n\) down to \(1\). Expanding it gives
\[ T(n) = T(n-1) + 1 = T(n-2) + 2 = \cdots = T(1) + (n-1) = n \]
So \(T(n) = n\), which is \(\Theta(n)\). Option (A) qualifies.

Step 3: Check option (B).
\[ T(n) = 2T\left(\frac{n}{2}\right) + 1, \quad T(1) = 1 \]
By the Master Theorem, here \(a = 2\), \(b = 2\), so \(n^{\log_b a} = n^{\log_2 2} = n\). The extra work term \(f(n) = 1\) grows slower than \(n\) by a polynomial factor, so this falls under Master Theorem Case 1, giving \(T(n) = \Theta(n)\).
We can check this directly too. Let \(n = 2^k\), so \(T(2^k) = 2T(2^{k-1}) + 1\). Unrolling gives
\[ T(2^k) = 2^k T(1) + \left(2^{k-1} + 2^{k-2} + \cdots + 1\right) = 2^k + (2^k - 1) = 2 \cdot 2^k - 1 \]
Since \(n = 2^k\), this is \(T(n) = 2n - 1\), which is \(\Theta(n)\). Option (B) qualifies.

Step 4: Check option (C).
\[ T(n) = 2T\left(\frac{n}{2}\right) + n, \quad T(1) = 1 \]
Here \(a = 2\), \(b = 2\), \(f(n) = n\), and \(n^{\log_b a} = n\). Since \(f(n) = \Theta(n^{\log_b a})\), this is Master Theorem Case 2, so
\[ T(n) = \Theta(n \log n) \]
This is the familiar merge sort recurrence, and \(n \log n\) grows faster than \(n\), so it is not \(\Theta(n)\). Option (C) does not qualify.

Step 5: Check option (D).
\[ T(n) = T(n-1) + n, \quad T(1) = 1 \]
Expanding gives
\[ T(n) = n + (n-1) + (n-2) + \cdots + 1 = \frac{n(n+1)}{2} \]
This is \(\Theta(n^2)\), quadratic growth, not linear. Option (D) does not qualify.

Final Answer:
Options (A) and (B) give recurrences that solve to \(\Theta(n)\).
\[ \boxed{\text{(A) and (B)}} \]