Question

What is the time complexity of Kruskal’s algorithm?

(a) O(log V)

(b) O(E log V)

(c) O(E^2)

(d) O(V log E)

This question was addressed to me in a national level competition.

This key question is from Minimum Spanning Tree in section Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

Correct answer is (b) O(E log V)

The explanation is: Kruskal’s algorithm involves sorting of the edges, which takes O(E logE) time, where E is a number of edges in graph and V is the number of vertices. After sorting, all edges are iterated and union-find algorithm is applied. union-find algorithm requires O(logV) time. So, overall Kruskal’s algorithm requires O(E log V) time.