Match the following algorithm with its standard time complexity: Algorithms:…
2016
Match the following algorithm with its standard time complexity:
Algorithms:
a. Prim’s algorithm
b. Bellman-Ford algorithm
c. Floyd-Warshall algorithm
d. Johnson’s algorithm
Complexities:
i. O(VE)
ii. O(VE log V)
iii. O(E log V)
iv. O(V³)
Here, V is the set of vertices and E is the set of edges in the graph. Choose the correct matching.
- A.
a-i, b-iii, c-iv, d-ii
- B.
a-i, b-iii, c-ii, d-iv
- C.
a-iii, b-i, c-iv, d-ii
- D.
a-iii, b-i, c-ii, d-iv
Attempted by 145 students.
Show answer & explanation
Correct answer: C
Correct matching: a-iii, b-i, c-iv, d-ii.
Prim’s algorithm, with a binary heap and adjacency list, is commonly O(E log V).
Bellman-Ford relaxes all edges for up to V − 1 passes, so its standard single-source shortest-path time complexity is O(VE).
Floyd-Warshall uses three nested loops over vertices, so it is O(V³).
Johnson’s algorithm is represented in this option set as O(VE log V).