The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.1k 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 (68.8k points)
edited by | 1.1k views
e cant be possible

2 Answers

+13 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.9k points)
edited by

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.

 

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 :)
@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.

To be precise I think it should be O(mlogm+ m) .... correct me if i am wrong ...

refer this ......

0 votes
answered by Veteran (48.6k 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

32,620 questions
39,267 answers
109,738 comments
36,656 users