Arrange the following recurrence relations in increasing order of their time complexity: (A) T(n) = T(n/2) + 1 (B) T(n) = 2T(n/2) + n (C) T(n) = 3T(n/3) + n (D) T(n) = 2T(n/2) + √n (E) T(n) = T(n−1) + 1

1. A(E), (A), (B), (D), (C)
2. B(A), (E), (D), (B), (C)
3. C(E), (A), (D), (B), (C)
4. D(A), (B), (D), (E), (C)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. (A), (E), (D), (B), (C)

Explanation

(A) is Θ(log n); (E) and (D) are Θ(n); (B) and (C) are Θ(n log n). So A, E, D, B, C.