Match each graph algorithm with its time complexity (n vertices, m edges). List I: A. Bellman-Ford, B. Kruskal's algorithm, C. Floyd-Warshall, D. Topological sorting. List II: I. O(m log n), II. O(n³), III. O(n·m), IV. O(n + m).

1. AA ‐ III, B ‐ I, C ‐ II, D ‐ IV
2. BA ‐ II, B ‐ IV, C ‐ III, D ‐ I
3. CA ‐ III, B ‐ IV, C ‐ I, D ‐ II
4. DA ‐ II, B ‐ I, C ‐ III, D ‐ IV

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

Show answer & explanation

Correct answer: A. A ‐ III, B ‐ I, C ‐ II, D ‐ IV

Explanation

Bellman–Ford is O(nm); Kruskal is O(m log n); Floyd–Warshall is O(n³); topological sort is O(n + m).