Which of the following can be recurrence relation(s) corresponding to an…
2026
Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity Θ(n)?
Answer: A. T(n)=T(n−1)+1 𝑇(1) = 1; B. T(n)=2T(n/2)+1 𝑇(1) = 1 — To determine the time complexity, we analyze each recurrence relation individually. Option A: T(n) = T(n-1) + 1. Expanding this gives T(n) = T(1) + (n-1).…
- A.
T(n)=T(n−1)+1 𝑇(1) = 1
- B.
T(n)=2T(n/2)+1 𝑇(1) = 1
- C.
T(n)=2T(n/2)+n 𝑇(1) = 1
- D.
T(n)=T(n−1)+n 𝑇(1) = 1
Attempted by 26 students.
Show answer & explanation
Correct answer: A, B
To determine the time complexity, we analyze each recurrence relation individually.
Option A: T(n) = T(n-1) + 1. Expanding this gives T(n) = T(1) + (n-1). Since T(1) is constant, the complexity is Theta(n).
Option B: T(n) = 2T(n/2) + 1. Using the Master Theorem, a=2, b=2, f(n)=1. Since n^log_b a = n dominates f(n), the complexity is Theta(n).
Option C: T(n) = 2T(n/2) + n. Here a=2, b=2, f(n)=n. Since f(n) matches n^log_b a, the complexity is Theta(n log n).
Option D: T(n) = T(n-1) + n. This sums integers from 1 to n, resulting in a quadratic complexity of Theta(n^2).
Conclusion: Options A and B correspond to an algorithm with time complexity Theta(n).
A video solution is available for this question — log in and enroll to watch it.