Correct : a,b

To find the time complexity of Θ(n), we need to solve each recurrence relation to see which ones evaluate to linear time.

Option A: T(n) = T(n-1) + 1
Using the substitution method:
T(n) = T(n-2) + 1 + 1 = T(n-2) + 2
Continuing this k times gives us: T(n) = T(n-k) + k.
When we reach the base case T(1), we set n-k = 1, which means k = n-1.
Substituting k back into the equation: T(n) = T(1) + (n-1) = 1 + n - 1 = n.
Therefore, the time complexity is Θ(n). This is correct. ✓

Option B: T(n) = 2T(n/2) + 1
We can solve this using the Master Theorem for divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).
Here, a = 2, b = 2, and f(n) = 1.
First, we calculate n^log_ba = n^log₂2 = n¹ = n.
Now we compare f(n) with n. Since f(n) = 1 is polynomially smaller than n, this falls strictly under Case 1 of the Master Theorem.
Therefore, the time complexity is bounded by n^log_ba, which gives us Θ(n). This is also correct. ✓

Option C: T(n) = 2T(n/2) + n
Using the Master Theorem again:
Here, a = 2, b = 2, and f(n) = n.
Comparing f(n) with n^log_ba = n¹ = n.
Since f(n) and n^log_ba are exactly equal, this falls under Case 2 of the Master Theorem. We must multiply by log n.
The time complexity is Θ(n log n). This is incorrect. ✗

Option D: T(n) = T(n-1) + n
Using the substitution method again:
T(n) = T(n-2) + (n-1) + n
If we continue this down to the base case, we get the sum of the first n integers:
T(n) = T(1) + 2 + 3 + ... + n
The sum of the first n integers is n(n+1)/2. Expanding this gives n²/2 + n/2, where the highest order term is n².
The time complexity is Θ(n²). This is incorrect. ✗

Correct Answer: A and B ✓