In the following table, the left column contains the names of standard graph…
2021
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. Here, n and m are number of vertices and edges, respectively. Match each algorithm with its time complexity.
Choose the correct answer from the options given below:
- A.
A ‐ III, B ‐ I, C ‐ II, D ‐ IV
- B.
A ‐ II, B ‐ IV, C ‐ III, D ‐ I
- C.
A ‐ III, B ‐ IV, C ‐ I, D ‐ II
- D.
A ‐ II, B ‐ I, C ‐ III, D ‐ IV
Attempted by 87 students.
Show answer & explanation
Correct answer: A
Correct matching:
Bellman-Ford → O(nm)
Kruskal’s algorithm → O(m log n)
Floyd-Warshall algorithm → O(n^3)
Topological sorting → O(n+m)
Brief justification:
Bellman-Ford: relaxes all edges up to n−1 times, giving O(nm).
Kruskal: sorts the m edges (dominant cost O(m log m) which is commonly written as O(m log n)), then uses union-find for near-linear additional time.
Floyd-Warshall: uses three nested loops over vertices, so O(n^3).
Topological sorting: can be done with DFS or Kahn’s algorithm in linear time proportional to vertices plus edges, O(n+m).
Note: The originally marked correct option was inconsistent with these standard complexities; use the mappings and justifications above.
A video solution is available for this question — log in and enroll to watch it.