First time here? Checkout the FAQ!
+6 votes
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 in Algorithms by Veteran (64.6k points)  
retagged by | 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.

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?

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


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.

Related questions

Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2092 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points

26,038 questions
33,651 answers
31,069 users