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