GATE IT 2005 | Question: 15

Question

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.$$\begin{array}{|ll|ll|}\hline \text{1.} & \text{Bellman-Ford algorithm} & \text{A:} & \text{$O(m\log n)$} \\\hline  \text{2.} & \text{Kruskal’s algorithm} & \text{B:}& \text{$O(n^3)$} \\\hline   \text{3.}& \text{Floyd-Warshall algorithm} & \text{C:}  & \text{$O(nm)$} \\\hline  \text{4.} & \text{Topological sorting} &\text{D:}  & \text{$O(n+m)$}  \\\hline \end{array}$$

• A. $\text{1→ C, 2 → A, 3 → B, 4 → D}$
• B. $\text{1→ B, 2 → D, 3 → C, 4 → A}$
• C. $\text{1→ C, 2 → D, 3 → A, 4 → B}$
• D. $\text{1→ B, 2 → A, 3 → C, 4 → D}$

Answer 1

1. Bellman-Ford algorithm $\implies \text {option} (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 $\implies$ Remaining Option $(A)$ :  $O ( m \log n)$.
3. Floyd-Warshall algorithm $\implies$ option $(B)$, Dynamic Programming Algo, $O(N^3)$.
4. Topological sorting $\implies \text {option} (D)$,  boils down to DFS, $O(V+E)$.

Answer (A).

Comments

$\text{Kruskal's algorithm using union-find:} \\ \text{Time Complexity = Time taken for sorting edges + Picking edges one by one} \\ \text{from sorted edges so that it does not form a cycle} \\ = O(mlogm) + O(1) * O(m) \\ ( \because \text{ O(1) to check cycle using union find) } \\ = O(mlogm) + O(m) \\ = O(m log n^2) \left (\text {As m} = O(n^{2}) \right ) \\ = O(2mlogn) \\ = O(mlogn)$

Answer 2

Option a you can get it from any standard book