retagged by
13,807 views
43 votes
43 votes

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)$
retagged by

3 Answers

Best answer
36 votes
36 votes

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/

edited by
5 votes
5 votes

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

Answer:

Related questions

21 votes
21 votes
1 answer
2