## 3 Answers

Answer: B, D, 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/

### 20 Comments

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.

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

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.

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

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

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.

Since m=O(n

^{2}) in a graph, options B and E are also correct as big-O specifies asymptotic upper bound only.

Though your answer is correct, this reasoning is very much wrong. B is right cause logn = O(n) ; E is right cause m= theeta(n) and n=theeta(m) ; so logn = O(m); thus mlogn = O(m*m) (just multiplied both sides by m). m = O(n^{2}) proves nothing.

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}).