The Gateway to Computer Science Excellence
+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)
in Algorithms by | 263 views

2 Answers

+2 votes
$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.
by
0 votes
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.
by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,482 answers
201,810 comments
95,283 users