+6 votes
651 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:

(a). $O(n^{2})$

(b). $O(mn)$

(c). $O(m+n)$

(d). $O(m \log n)$

(e). $O(m^2)$
asked
retagged | 651 views

## 2 Answers

+8 votes
Best answer
Answer: D, B, E

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/
answered by Veteran (35k points)
edited 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 :)

0 votes
answered by Veteran (43.8k points)
Yes D is correct but B and E too. D is tightest bound.
They are asking for time complexity.

+8 votes
3 answers
1
+6 votes
3 answers
2
+8 votes
2 answers
3