The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+7 votes
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)$
asked in Algorithms by Veteran (67.5k points)
edited ago by | 795 views
e cant be possible

2 Answers

+9 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 (35.5k points)
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?

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

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,946 questions
36,792 answers
91,068 comments
34,689 users