37 votes 37 votes Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______ Algorithms gate1992 spanning-tree algorithms time-complexity easy fill-in-the-blanks + – Kathleen asked Sep 12, 2014 retagged Apr 18, 2021 by Lakshman Bhaiya Kathleen 17.3k views answer comment Share Follow See 1 comment See all 1 1 comment reply -RahulKumar- commented Oct 23, 2023 reply Follow Share Answer should be: $O(E)$ 0 votes 0 votes Please log in or register to add a comment.
–1 votes –1 votes ANSWER SHOULD BE O(V+E). rajoramanoj answered Aug 18, 2017 rajoramanoj comment Share Follow See 1 comment See all 1 1 comment reply Rahul Kumar Rohilla commented Sep 5, 2017 reply Follow Share Answer will be O(E LogV) because we have to check for all the edges if there is any cycle while including in MST. Some have given answer O(E+V) which is wrong. 1 votes 1 votes Please log in or register to add a comment.
–2 votes –2 votes Though edges are sorted still due to union find operation complexity is O(mlogn). Gate Mission 1 answered Jan 2, 2017 Gate Mission 1 comment Share Follow See all 0 reply Please log in or register to add a comment.