The Gateway to Computer Science Excellence

+23 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:

- $O(n^{2})$
- $O(mn)$
- $O(m+n)$
- $O(m \log n)$
- $O(m^2)$

+18 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 $m = O\left(n^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/

+10

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)

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

@VS,

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

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

+6

@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(V^{2}lgV)=O(n^{2}lgn)

and hence (a) wrong

Thanks for pointing out :)

+8

It should be m=O(n^{2}) 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

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

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.

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

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)

+1

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.

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.

+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=V^{2}}^{ }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 (M^{2}).

52,345 questions

60,470 answers

201,796 comments

95,273 users