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}$

Comments

this classifies under theory/meemory based question?

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)$

---

confused and put option d

Answer 2

Option a you can get it from any standard book