Match each algorithm with its running time. (A) Breadth-first search, (B) Rabin–Karp algorithm, (C) Depth-first search, (D) Heap sort (worst case), (E) Quick sort (worst case). Times: (I) Θ(V + E), (II) O(V + E), (III) Θ((n − m + 1)m), (IV) O(n²), (V) O(n log n).

1. A(A)-(III), (B)-(II), (C)-(I), (D)-(IV), (E)-(V)
2. B(A)-(II), (B)-(III), (C)-(I), (D)-(V), (E)-(IV)
3. C(A)-(II), (B)-(III), (C)-(I), (D)-(V), (E)-(IV)
4. D(A)-(III), (B)-(I), (C)-(II), (D)-(IV), (E)-(V)

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

Show answer & explanation

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

Explanation

CLRS states BFS as O(V + E) and DFS as Θ(V + E); Rabin–Karp's worst case is Θ((n − m + 1)m); heap sort is O(n log n) in the worst case; quick sort's worst case is O(n²).

Note: As printed, options B and C are identical, so either is correct; the official key is C.