Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
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:
| List I | List II |
|---|---|
| A. Bellman-Ford algorithm | I. $O(m\log n)$ |
| B. Kruskal's algorithm | II. $O(n^3)$ |
| C. Floyd-Warshall algorithm | III. $O(n*m)$ |
| D. Topological sorting | IV. $O(n+m)$ |
Solution
Bellman-Ford algorithm checks all edges repeatedly for shortest path, so its time complexity is $O(n*m)$. Thus, $A-III$.Kruskal's algorithm sorts edges and then applies union-find, so its time complexity is $O(m\log n)$. Thus, $B-I$.
Floyd-Warshall algorithm uses three nested loops for all pairs shortest path, so its time complexity is $O(n^3)$. Thus, $C-II$.
Topological sorting visits vertices and edges once, so its time complexity is $O(n+m)$. Thus, $D-IV$.
Final matching is $A-III,\ B-I,\ C-II,\ D-IV$.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
