5 votes 5 votes 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: $O(mn)$ $O(m)$ $O(m+n)$ $O(n)$ Algorithms nielit2016dec-scientistb-it algorithms spanning-tree time-complexity + – admin asked Mar 31, 2020 • retagged Aug 23, 2020 by Lakshman Bhaiya admin 1.8k views answer comment Share Follow See 1 comment See all 1 1 comment reply abhishek tiwary commented Apr 28, 2020 reply Follow Share https://gateoverflow.in/549/gate1992-01-ix 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes 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 Mohit Kumar 6 answered May 29, 2020 Mohit Kumar 6 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes O(m) is the answer , as the edges are already sorted we donot need to sort them , therefore union operation takes O(E) time , where E is the no. of edges . Sanandan answered Sep 11, 2020 Sanandan comment Share Follow See all 0 reply Please log in or register to add a comment.