Dark Mode

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