In the following table, the left column contains the names of standard graph…
2005
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.
1. Bellman-Ford algorithm | A : O ( m log n) |
2. Kruskal’s algorithm | B : O (n3) |
3. Floyd-Warshall algorithm | C : O (nm) |
4. Topological sorting | D : O (n + m) |
- A.
1→ C, 2 → A, 3 → B, 4 → D
- B.
1→ B, 2 → D, 3 → C, 4 → A
- C.
1→ C, 2 → D, 3 → A, 4 → B
- D.
1→ B, 2 → A, 3 → C, 4 → D
Attempted by 97 students.
Show answer & explanation
Correct answer: A
Correct matching: Bellman–Ford → O(nm); Kruskal’s → O(m log n); Floyd–Warshall → O(n^3); Topological sorting → O(n + m).
Bellman–Ford: O(nm). Rationale: for single-source shortest paths with possible negative weights, the algorithm relaxes every edge up to (n−1) times, giving O(V·E).
Kruskal’s algorithm: O(m log n). Rationale: sorting the edges dominates the cost (O(m log m) which is O(m log n)), plus nearly-linear union-find operations.
Floyd–Warshall: O(n^3). Rationale: computes all-pairs shortest paths using three nested loops over vertices.
Topological sorting: O(n + m). Rationale: using DFS or Kahn’s algorithm visits each vertex and each edge once.