in Algorithms retagged by
1,795 views
5 votes
5 votes

Complexity of Kruskal's algorithm for finding minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is:

  1. $O(mn)$
  2. $O(m)$
  3. $O(m+n)$
  4. $O(n)$
in Algorithms retagged by
by
1.8k views

1 comment

0
0

2 Answers

5 votes
5 votes

Option B O(m)

Implementation of Kruskal's algorithm should be implemented in 2 steps:
Step1: Sorting of edges takes $O(E*log(E))$ time.
Step2: After sorting, we iterate through all edges and apply find union algorithm.

The find and union operations can take at most $O(1)$ time if you use Disjoint set. So overall complexity is$ O(Elog(E) + E)$ time.
Given the edges are already sorted, so we need to do only second step i.e.,we iterate through all edges and apply find-union algorithm. The find and union operations can take at most $O(1)$ time. So, the total time complexity will be $O(E)$.

https://www.youtube.com/watch?v=fAuF0EuZVCk

0 votes
0 votes
O(m) is the answer , as the edges are already sorted we donot need to sort them , therefore union operation takes O(E) time , where E is the no. of edges  .