Complexity of Kruskal's algorithm for finding minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is:
https://gateoverflow.in/549/gate1992-01-ix
Option B O(m)
Implementation of Kruskal's algorithm should be implemented in 2 steps: Step1: Sorting of edges takes $O(E*log(E))$ time. Step2: After sorting, we iterate through all edges and apply find union algorithm.
The find and union operations can take at most $O(1)$ time if you use Disjoint set. So overall complexity is$ O(Elog(E) + E)$ time. Given the edges are already sorted, so we need to do only second step i.e.,we iterate through all edges and apply find-union algorithm. The find and union operations can take at most $O(1)$ time. So, the total time complexity will be $O(E)$.
https://www.youtube.com/watch?v=fAuF0EuZVCk
64.3k questions
77.9k answers
244k comments
80.0k users