2.4k 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 | 2.4k views
0
e cant be possible

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.

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

answered by Boss (33.8k points)
edited
+14

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

then the answer will be changed

+7

Tightest upper bound is $\color{blue} d$ but b and e are also correct here.
Simple but nice catch. :)

+2
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)
+1
a should also be correct.
–1
How b can be?
0
@VS,

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

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

+5

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.

+1
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
0

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

@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)$

0
@ rahul

iam not able to understand properly from the comments

can you explain the entire concept of how the options are chosen if possible :)
+1
@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.
+1

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

refer this ......

0

@rahul sharma 5 can you explain how logm = O(m) I'm stuck at this point else I got your answer perfectly!

0

iarnav upper bound of log(m) is o(m) because polynomial(m) is always more than logarithmic fxn(logm)

0
Thanks Bhai.
0
Kruskal's running time when graph is sparse is O(ElogV). But when graph is dense(more or less like complete graph) then E=n(n-1)/2 ~= O(n^2).

So O(mlogn) = O(n^2logn),  Now consider all option and replace m with n^2 in options given above. In option B O(mn)=O(n^3) which is big oh of O(n^2logn). Similerly O(m^2) =O(n^4) which is big oh of O(n^2logn). So Option B,D,E are correct.
0

@rahul sharma 5  is ans will be d) if it is for tightest upper bound

0

@rahul Sharma 5, i think Shatadru RC is right.

it should be log v = O(log m).

please correct me, if wrong

+1 vote
answered by Boss (41k points)
+2
Yes D is correct but B and E too. D is tightest bound.
They are asking for time complexity.
+1 vote

The accurate answer is option D that is time complexity for Kruskal's algo.

[ for adjacency list = O(ElogE), for matrix representation {at max E=V2}  O(2*ElogV) ] Or (E*logV) or O (M*logN).

In general case or worst case we consider matrix representation so time complexity O (ElogV).

now coming to the question again

in worst case logN = O(N) so option B is also right O (M*N)

and since N = O(M) so option E is also right O (M2).

answered by Active (1.8k points)

1
2