The Gateway to Computer Science Excellence
0 votes
121 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 Active (3.5k points) | 121 views

2 Answers

+1 vote
$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 Active (2.3k points)
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 Active (2.8k points)
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
50,647 questions
56,491 answers
195,436 comments
100,669 users