1. Computer Science Engineering (CSE)
  2. Design and Analysis of Algorithms
  3. What is the time complexity of Kruskal’s...

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)
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.