The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
2.7k views
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 sorted is _______
asked in Algorithms by Veteran (59.6k points) | 2.7k views

5 Answers

+21 votes
Best answer

If all edges are already sorted then this problem will reduced to union-find problem on a graph with $E$ edges and $V$ vertices.

for each edge (u,v) in E

    if(FIND-SET(u) != FIND-SET(v))
        UNION(u,v)

FIND-SET$(v)$ and UNION$(u,v)$ runs in $α(|V|)$

where $α(n)$ is inverse ackermann function i.e $\log^*(n)$

So, overall complexity becomes $O(|E|.α(|V|))$

answered by Boss (13.6k points)
edited by
+2
answer should be $O(ElogV)$ using disjoint data structure..
0

reena_kandari But here nothing is mentioned about completeness or not ! so its could be $n^2logn$ or $mlogn$ correct me if i am wrong?

0
@Reena

Since edges are already sorted , So it will not take O(ElogV) using disjoint data structure..
0
#reena can u tell me y it is O(ElogV) ??
0

@reena_kandari  But that time complexity of O(ElogV) is for the whole 'Krushkal minimum spanning tree' algorithm, i.e, when the edges need to be sorted. According to the question the edges have already been sorted, so O(ElogV) is irrelevant here. Only need to consider union find operation on the E edges and each union find operation takes a constant amount of time, video posted above by @Puja Mishra explains this. Thus O(1)E (E times O(1)), = O(E).

+1
Kruskal algorithm:-

step 1: sort the all edges

step 2: for each edge $E$ from sorted list add it to kruskal forest and check if it doesn't form a cycle--

using union find data structure it will take $E$*$logV$ .here $log V$ is TC of "find" and "union" operation.

some are saying that we can use DFS here but after adding each edge we have to run DFS as many times as edges are i.e.$E*O(V+E)$. if we do aggregate analysis here it cannt be smaller that $E(logV)$.
0

@reena_kandari  the amortized version of union find runs in O(1), check https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

Quote from above geeksforgeeks page 

The time complexity of each operations becomes even smaller than O(Logn). In fact, amortized time complexity effectively becomes small constant.

0
this is space complexity
+1

When, we have our edges sorted, then we only perform UNION and FIND-SET operations on all edges of graph to form MST.

Total number of times UNION and FIND-SET are called=$|E|$ times max

So, time complexity is given by $O(E(\alpha(n)))$ where $\alpha(n)$ is a very slowly growing function.

How slowly is grows is below explained by snapshot form Cormen.

so $\alpha(n)=4$ even for very very large values of n. Hence a constant.

Hence, my running time reduces to $O(E)$ only.

0

If edge weights are unsorted then running time $\in$ $O(sort(|E|) + |E|*\alpha(V) + |V|)$ using Disjoint-Set data structure..

If edge weights are sorted then running time $\in$ $O(|E|*\alpha(V)  + |V|)$ $=$ $O(E)$

If edge weights are small like {1,2,3,....,$n^{c}$} Then we can  use radix sort for $sort(|E|)$ and it will take linear time in terms of number of edges  otherwise Prim's algo will be better...

for all practical sized input,  $log*n$ is always $\leqslant$ 4
Because if we take $n$ as $2^{65536} = 2^{2^{16}}$= $2^{2^{2^{2^{2}}}}$... Now if we calculate $log*n$, here.. It will give 4.
So for all practical purposes, we use  $log*n \leqslant 4$.

+1 vote

Time complexity for the whole 'Krushkal minimum spanning tree' algorithm, i.e, when the edges need to be sorted is O(ElogV). According to the question the edges have already been sorted, so O(ElogV) is irrelevant here. Only need to consider union find operation on the E edges and each union find operation takes a constant amount of time, video posted below explains this. Thus O(1)E (E times O(1)), = O(E). The time complexity of the accepted answer is the case when 'path compression' and 'union by rank' methods have not been implemented. For amortized union find operation which implements 'path compression' and 'union by rank' methods, the time complexity is O(1) [Check geeksforgeeks link below]. Thus time complexity for this question should be O(E)

https://www.youtube.com/watch?v=fAuF0EuZVCk

https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

answered by (141 points)
0 votes
Find operation will take at most  ~2m time
& union operation will take at most  ~nlogn
So overall complexity = 2m+nlogn
& the biggest term is mlogn since m>n for connected graph where
 m is no.  of Edges & n is no.of vertices
answered by (11 points)
–2 votes
Though edges are sorted still due to union find operation complexity is O(mlogn).
answered by Active (4k points)
–2 votes
ANSWER SHOULD BE O(V+E).
answered by Active (4.5k points)
+1
Answer will be O(E LogV)  because we have to check for all the edges if there is any cycle while including in MST.

Some have given answer O(E+V) which is wrong.


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

41,084 questions
47,676 answers
147,486 comments
62,394 users