Consider the following algorithms and their running times:
| Algorithms | Complexities | ||
| (A) | Breadth First Search | (I) | θ(v + E) |
| (B) | Rabin-Karp Algorithm | (II) | O(v + E) |
| (C) | Depth-First Search | (III) | θ((n − m − 1)m) |
| (D) | Heap sort (worst case) | (IV) | O(n2) |
| (E) | Quick sort (worst case) | (V) | O(n lg n) |
Which one of the following is correct?
1
(A) - (III), (B) - (II), (C) - (I), (D) - (IV), (E) - (V)
2
(A) - (II), (B) - (III), (C) - (I), (D) - (IV), (E) - (V)
3
(A) - (II), (B) - (III), (C) - (I), (D) - (V), (E) - (IV)
4
(A) - (III), (B) - (I), (C) - (II), (D) - (IV), (E) - (V)