What is the time complexity of Kruskal’s algorithm?
|B.||o(e log v)|
|D.||o(v log e)|
|Answer» B. o(e log v)|
|Explanation: 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.|
Login to Continue
It will take less than 2 minutes