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

Let us solve each recurrence relation:

• Option (A): $T(n) = T(n - 1) + 1$ with $T(1) = 1$.

  $$T(n) = T(n - 1) + 1 = T(n - 2) + 2 = \dots = T(1) + (n - 1) = 1 + n - 1 = n = \Theta(n)$$

• Option (B): $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(1) = 1$. Using the Master Theorem $T(n) = aT(n/b) + f(n)$ where $a = 2, b = 2, f(n) = 1$:

  $$n^{\log_b a} = n^{\log_2 2} = n^1 = n$$

  Since $f(n) = 1 = O(n^{1 - \epsilon})$ for $\epsilon = 1$, by Case 1 of the Master Theorem:

  $$T(n) = \Theta(n)$$

• Option (C): $T(n) = 2T\left(\frac{n}{2}\right) + n$ with $T(1) = 1$. Here $a = 2, b = 2, f(n) = n = \Theta(n^{\log_2 2})$. By Case 2 of the Master Theorem:

  $$T(n) = \Theta(n \log n)$$

• Option (D): $T(n) = T(n - 1) + n$ with $T(1) = 1$.

  $$T(n) = T(1) + 2 + 3 + \dots + n = \frac{n(n + 1)}{2} = \Theta(n^2)$$

Therefore, the recurrence relations with time complexity $\Theta(n)$ are (A) and (B).