23 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 sorted is _______

32 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|))$

15

When the edges are already sorted then, The problem of finding the minimum spanning tree reduces to detecting if there is a cycle in the graph or not.

I mean since edges are already sorted, take each edge one by one and add to mst (if no cycle is formed).

Now, detecting whether an undirected graph has a cycle or not can be done ::

1) Either using DFT or BFT :: O(V+E)

2)Using Union-Find :: O(ElogV)

I mean since edges are already sorted, take each edge one by one and add to mst (if no cycle is formed).

Now, detecting whether an undirected graph has a cycle or not can be done ::

1) Either using DFT or BFT :: O(V+E)

2)Using Union-Find :: O(ElogV)

1

@ VS:-

How many times you will apply BFS?It needs to be applies for every egde.

Also, for you point it should be E*loge ,because e times we will apply cycle detection algorithm and each time it takes log e time.

so it should be eloge

How many times you will apply BFS?It needs to be applies for every egde.

Also, for you point it should be E*loge ,because e times we will apply cycle detection algorithm and each time it takes log e time.

so it should be eloge

0

@Vikrant singh time complexity of union-find is O(ElogV) according to geeksforgeeks. How is it being said as Elog^*(n)??

2

so it should be mlogn ,right? Union find works in log n time and for each edge we traverse we check if cycle is there or not(in a graph of n vertices) ,taking logn time.

So answer mLogn is correct?m edges and n vertices.

So answer mLogn is correct?m edges and n vertices.

0

I think the answer should simply be O(E)

https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find

According to wikipedia amortized time complexity of unoin find is O(log*V), as Arjun said in one other answer log*n is practically a constant. For E unoin find operations, the answer would simply be E*O(1), Therefore O(E)

4

Complexity of kruskal is O(ElogE + E) .... ElogE for sorting the edges and E for union operation of E edges ...

So here it is sorted ... so O(E) ... correct me if i am wrong ... Refer this ...

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

Since edges are already sorted , So it will not take O(ElogV) using disjoint data structure..

1

@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).

3

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

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

1

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

15

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.

3

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

0

First of all we need to make set of each vertices. so, that when we ask FIND-SET(v) then it should output v initially.

for each vertex V in graph G

MAKE-SET(V) // make set with only vertex V in it.

// edges are already sorted so, now we have to just add edges in order given if they don't form cycle.

for each edge (u,v) that belong to G

{

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

T = T U {u,v} // T here is tree that needs to be constructed.

UNION( u,v) // that is unify two sets whose representative are u and v.

}

so , time complexity = |V| * α(V) time for making subset for each vertex + |E|*α(V) time checking whether cycle exists or not. as FIND-SET and UNION runs in O(1) time

=O(( |V| + |E|)*α(V))

generally , α(n) is constant even for very large value of n

so , time required = O(m + n)

for each vertex V in graph G

MAKE-SET(V) // make set with only vertex V in it.

// edges are already sorted so, now we have to just add edges in order given if they don't form cycle.

for each edge (u,v) that belong to G

{

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

T = T U {u,v} // T here is tree that needs to be constructed.

UNION( u,v) // that is unify two sets whose representative are u and v.

}

so , time complexity = |V| * α(V) time for making subset for each vertex + |E|*α(V) time checking whether cycle exists or not. as FIND-SET and UNION runs in O(1) time

=O(( |V| + |E|)*α(V))

generally , α(n) is constant even for very large value of n

so , time required = O(m + n)

7 votes

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/

1 vote

First of all we need to make set of each vertices. so, that when we ask FIND-SET(v) then it should output v initially.

for each vertex V in graph G

MAKE-SET(V) // make set with only vertex V in it.

// edges are already sorted so, now we have to just add edges in order given if they don't form cycle.

for each edge (u,v) that belong to G

{

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

T = T U {u,v} // T here is tree that needs to be constructed.

UNION( u,v) // that is unify two sets whose representative are u and v.

}

so , time complexity = |V| time for making subset for each vertex + |E| time checking whether cycle exists or not. as FIND-SET and UNION runs in O(1) time

=O( |V| + |E|)

=O(m+n)

for each vertex V in graph G

MAKE-SET(V) // make set with only vertex V in it.

// edges are already sorted so, now we have to just add edges in order given if they don't form cycle.

for each edge (u,v) that belong to G

{

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

T = T U {u,v} // T here is tree that needs to be constructed.

UNION( u,v) // that is unify two sets whose representative are u and v.

}

so , time complexity = |V| time for making subset for each vertex + |E| time checking whether cycle exists or not. as FIND-SET and UNION runs in O(1) time

=O( |V| + |E|)

=O(m+n)

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

& 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

0 votes

Since the edges are sorted, we simply need to visit the vertex, and select an edge.

Now, **Selecting an edge means, check if the edge creates a cycle or not and if not then insert. It does not consume a lot of time, we can assume it to be an O(1) operation.**

So we need to visit all the vertices: O(n)

And we need to perform **Select **operation for m edges: O(m) **(worst case)**.

So overall time complexity is **O(m+n).**

–1 vote