The Time complexity of Kruskal’s Algorithm is:
$O(E \cdot logE + E \cdot \alpha)$
Where the term:
$E \cdot logE$ $=>$ Time required for sorting the edges
$E \cdot \alpha$ $=>$ Time required to find the cycle (which is equal to $\alpha$) for each Edge $E$.
Interestingly there are two ways to find a cycle in a graph, which takes time as:
- DFS: where $\alpha = O(V+E)$
- Union-Find Structure: where $\alpha = O(1)$
Generally, since Union-Find Structure (its not there in GATE syllabus till now) outperforms DFS in this case, we use the same for detecting cycle in minimum time.
Therefore, our total time complexity becomes: $O(E \cdot logE + E)$
Now, it was given in the question that edges are already sorted.
Hence Time complexity will be: $O(E)$