795 views

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

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)$
edited ago | 795 views
e cant be possible

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 $n = O\left(m^2\right)$ in a graph, options B and E are also correct as big-O specifies asymptotic upper bound only.

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

edited ago by

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

then the answer will be changed

How option (b) and (e) are also correct?

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.

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?

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