GEEKS FOR GEEKS GATE 2017 MOCK

Question

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)

Comments

Time complexity for initializing disjoint set i.e O(n) is not taken into account.

Ideally time complexity should be O(n+m).

Under the assumption that graph is a dense graph where m is O(n^2).

Time complexity becomes O(n+n^2)  = O(n^2) = O(m).

Answer 1

$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.

Answer 2

Option B) O(m), as the edges are already sorted and given that union operation takes O(1) time.

Answer 3

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.