Question

How to calculate time complexity of kruskal algorithm?

Answer 1

create a forest F (a set of trees), where each vertex in the graph is a separate treecreate a set S containing all the edges in the graphwhile S is nonempty and F is not yet spanning remove an edge with minimum weight from S if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree

Assuming that S is maintained as a min-heap, and the forest is Disjoint-set data structure , the remove minimum edge step will cost O(log e) and combine two trees will be O(log v) , therefore the total running time is O(e log e) or O(e log v). Both are equivalent as loge <= 2logv .