Match List I with List II and choose the correct answer from the code given…
2018
Match List I with List II and choose the correct answer from the code given below.
\(\begin{array} {clcl} & \textbf{List I} & & \textbf{List II} \\ & \textbf{(Graph Algorithm)} & & \textbf{(Time Complexity)} \\ \text{(a)} & \text{Dijkstra’s algorithm} & \text{(i)}& O(E \: lg \: E) \\ \text{(b)}& \text{Kruskal’s algorithm} & \text{(ii)}& \Theta(V^3) \\ \text{(c)} & \text{Floyd-Warshall algorithm} & \text{(iii)} & O(V^2) \\ \text{(d)} & \text{Topological sorting} & \text{(iv)}& \Theta(V+E) \\ \end{array}\)
where \(𝑉\) and \(𝐸\) are the number of vertices and edged in graph respectively.
\(\textbf{Code :}\)
- A.
\((a)-(i), (b)-(iii), (c)-(ii), (d)-(iv) \) - B.
\((a)-(iii), (b)-(i), (c)-(ii), (d)-(iv) \) - C.
\((a)-(i), (b)-(iii), (c)-(iv), (d)-(ii) \) - D.
\((a)-(iii), (b)-(i), (c)-(iv), (d)-(ii)\)
Attempted by 105 students.
Show answer & explanation
Correct answer: B
Final matching:
Dijkstra’s algorithm → O(V^2). Reason: Using a simple array-based implementation (selecting the minimum distance vertex by scanning all vertices) yields O(V^2). (With a binary heap or Fibonacci heap, the complexity can be reduced to O(E log V) or O(V log V + E), but those options are not among the given choices.)
Kruskal’s algorithm → O(E log E). Reason: Sorting the edges dominates the running time, giving O(E log E). Union-find operations are near-linear.
Floyd–Warshall algorithm → Θ(V^3). Reason: The algorithm uses three nested loops over vertices, leading to cubic time.
Topological sorting → Θ(V+E). Reason: Using DFS-based ordering or Kahn’s algorithm visits each vertex and edge a constant number of times, giving linear time in the graph size.
Therefore the correct pairing is: Dijkstra’s algorithm → O(V^2), Kruskal’s algorithm → O(E log E), Floyd–Warshall → Θ(V^3), Topological sorting → Θ(V+E).
A video solution is available for this question — log in and enroll to watch it.