1,593 views
1 votes
1 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 unsorted is _______

______________________________________________________________________________

If elements are sorted we do with Union Find algo with inverse of Ackermann function i.e.$O\left (|E|.\alpha |V| \right )$ , where $\alpha |V|$ is $log^{*}V$

Now from here can we derive it for unsorted edges?

for ref: here

1 Answer

Related questions

2 votes
2 votes
3 answers
2
Geet asked Oct 26, 2016
1,592 views
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
3 votes
3 votes
1 answer
3
Pooja Palod asked Oct 15, 2015
2,990 views
Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?
0 votes
0 votes
2 answers
4
radha gogia asked Aug 5, 2015
2,137 views
Does it tale constant time or the time taken proportional to search in the entire partition of elements to find whether the component lies in that same component or not ?...