Aptitude Overflow
+7 votes
429 views

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
 2. Kruskal’s algorithm
 3. Floyd-Warshall algorithm
 4. Topological sorting
 A : $O ( m \log n)$           
 B : $O (n^3)$
 C : $O (nm)$
 D : $O (n + m)$
  1. 1→ C, 2 → A, 3 → B, 4 → D
  2. 1→ B, 2 → D, 3 → C, 4 → A
  3. 1→ C, 2 → D, 3 → A, 4 → B
  4. 1→ B, 2 → A, 3 → C, 4 → D
asked in Algorithms by (21.5k points) 139 177 177 | 429 views

3 Answers

+12 votes
Best answer
  1. Bellman-Ford algorithm => C, $O (nm)$ Assuming $n$ as edges , $m$ as vertices, for every vertex we relax all edges. $m*n$ , $O(mn)$
  2. Kruskal’s algorithm => Remaining Option ,A : $O ( m \log n)$  
  3. Floyd-Warshall algorithm => B, Dynamic Programming Algo, $O(N^3)$
  4. Topological sorting =>D,  Boils Down to DFS, $O(V+E)$

Answer A

answered by (46.8k points) 3 12
edited by
+3 votes
Answer: A
answered by (35.6k points)
+1 vote
Option a you can get it from any standard book
answered by (13.6k points) 1 1

Related questions

2,724 questions
1,003 answers
393 comments
31,401 users