M

Mr. Dubey • 51.67K Points
Coach

Q. What is the time complexity of Kruskal’s algorithm?

(A) o(log v)
(B) o(e log v)
(C) o(e2)
(D) o(v log e)
Correct : Option (B)

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.

Share

Discusssion

Login to discuss.