7,538 views

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph $G$ with $n$ vertices and $m$ edges has the time complexity of:

1. $O(n^{2})$
2. $O(mn)$
3. $O(m+n)$
4. $O(m \log n)$
5. $O(m^2)$

e cant be possible
Using Fibonacci heap we can do it in O(n^2).Right?...So why isn’t that considered?

### Subscribe to GO Classes for GATE CSE 2022

When Union- Find algorithm is used to detect cycle while constructing the MST time complexity is $O(m \log n)$ where $m$ is the number of edges, and $n$ is the number of vertices. Since $m = O\left(n^2\right)$ in a graph, options B and E are also correct as big-O specifies asymptotic upper bound only.

Reference: http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/

i think m=O(n2) ; m=edges, n=vertices

then the answer will be changed

Tightest upper bound is $\color{blue} d$ but b and e are also correct here.
Simple but nice catch. :)

I have a doubt why (a) is wrong ??

Time Complexity of Kruskal = O ( (V-1) log E ) // Best Case

= O( (V-1)LogV ) = O(  V logV ) = O(V^2) or O(n^2)
a should also be correct.
How b can be?
@VS,

E could be greater than V-1.  V-1 is lower bound.  E- edges and V- vertices. So option A is not correct.

@Chhotu

Got it , if nothing given we consider the worst case scenarios in that case

E=V(V-1)/2 complete graph and tc=O(V2lgV)=O(n2lgn)

and hence (a) wrong

Thanks for pointing out :)

It should be  m=O(n2)  and not the other way as mentioned in answer.

m=(n*n-1 )/2 at max. so m=O(n^2)

Now answer with  O(mlogm) , as logm has upper bound as logn so it can also be O(mlogn).

O(mLogm) can also be written as O(m*m) ,it gives d and e as answer.

O(mlogn).can also be written as O(m*n) ,it gives b as answer.

edited
If n=4, m=O(n^2), so m can be at max 16.

Lg(n)=2, lg(m) =4. How can logn be upper bound of logm? @Rahul sharma

O(mLogm) can also be written as O(m*m) ,it gives d and e as answer.

O(mlogn).can also be written as O(m*n) ,it gives b as answer.

how log m can be m?

@Shatadru RC.Asymtotically bounds need not be mathematically equal.

$E=O(V^2)$.Now take log on both sides and prove.

set2018 :- $log m=O(m)$

@ rahul

iam not able to understand properly from the comments

can you explain the entire concept of how the options are chosen if possible :)
edited
@Rahul Sharma, If asymptotic calculations give some answer and in actual runtime it gives opposite result, then there's no point in studying algorithms. It has to be somewhat near to exact mathematical result.

Anyway, let's take some examples of  complete graph.

1. V=128, E(max) =8128

LogV=7, LogE=13

2. V=1024, E=523776

LogV=10, LogE=19

We can take many such examples that will prove LogV is always less than LogE.

Other than trees, for a connected graph it is always likely that no.of edges are greater than equals to no.of vertices. It is somewhat V <= E < V^2.

So it should be LogV = O(LogE)

I might be wrong. Pls have a second thought.

@rahul sharma 5 can you explain how logm = O(m) I'm stuck at this point else I got your answer perfectly!

iarnav upper bound of log(m) is o(m) because polynomial(m) is always more than logarithmic fxn(logm)

Thanks Bhai.
Kruskal's running time when graph is sparse is O(ElogV). But when graph is dense(more or less like complete graph) then E=n(n-1)/2 ~= O(n^2).

So O(mlogn) = O(n^2logn),  Now consider all option and replace m with n^2 in options given above. In option B O(mn)=O(n^3) which is big oh of O(n^2logn). Similerly O(m^2) =O(n^4) which is big oh of O(n^2logn). So Option B,D,E are correct.

@rahul sharma 5  is ans will be d) if it is for tightest upper bound

@rahul Sharma 5, i think Shatadru RC is right.

it should be log v = O(log m).

Since m=O(n2 ) in a graph, options B and E are also correct as big-O specifies asymptotic upper bound only.

Though your answer is correct, this reasoning is very much wrong. B is right cause logn = O(n) ; E is right cause m= theeta(n) and n=theeta(m) ; so logn = O(m); thus mlogn = O(m*m) (just multiplied both sides by m). m = O(n2) proves nothing.

The accurate answer is option D that is time complexity for Kruskal's algo.

[ for adjacency list = O(ElogE), for matrix representation {at max E=V2}  O(2*ElogV) ] Or (E*logV) or O (M*logN).

In general case or worst case we consider matrix representation so time complexity O (ElogV).

now coming to the question again

in worst case logN = O(N) so option B is also right O (M*N)

and since N = O(M) so option E is also right O (M2).

### 1 comment

Yes D is correct but B and E too. D is tightest bound.
They are asking for time complexity.