+1 vote
263 views

If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ?

 A O(m logn) B O(n) C O(m) D O(n logm)
| 263 views

$O(m)$. Because the edge weights are already sorted, now you may have to check m of the edges in the worst case as intermediate cycles could be formed when adding an edge.
option (c) is correct if in question it is not mention that find set and union take 0(1) time then time complexty will be ElogV i.e mlogn.