Match List I (recurrence) with List II (complexity). List I: (A) T(n) = 2T(n/2) + n, (B) T(n) = T(n/2) + 1, (C) T(n) = 2T(n/2) + 1, (D) T(n) = T(n−1) + n. List II: (I) T(n) = Θ(n log n) (exact), (II) O(n²), (III) T(n) = Θ(n) (exact), (IV) O(n).

1. A(A)-(I), (B)-(IV), (C)-(III), (D)-(II)
2. B(A)-(IV), (B)-(II), (C)-(I), (D)-(III)
3. C(A)-(I), (B)-(III), (C)-(IV), (D)-(II)
4. D(А)-(III), (B)-(I), (C)-(IV), (D)-(II) ∀x ∃ y(x < y)

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

Show answer & explanation

Correct answer: A. (A)-(I), (B)-(IV), (C)-(III), (D)-(II)

Explanation

2T(n/2) + n = Θ(n log n) (I). T(n/2) + 1 = Θ(log n), which is O(n) (IV) but not Θ(n). 2T(n/2) + 1 = Θ(n) exactly (III). T(n−1) + n = Θ(n²), i.e. O(n²) (II). That is option A.

Note on the official key: the official key says option C. Official/PW key is C, which pairs T(n) = T(n/2) + 1 with Θ(n) (exact). That recurrence is Θ(log n), so the pairing in option A is the correct one.