Question

Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?

(a) O(log V)

(b) O(V^2)

(c) O(E^2)

(d) O(V log E)

I had been asked this question during an interview.

Query is from Minimum Spanning Tree topic in portion Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

Right answer is (b) O(V^2)

The explanation is: Use of adjacency matrix provides the simple implementation of the Prim’s algorithm. In Prim’s algorithm, we need to search for the edge with a minimum for that vertex. So, worst case time complexity will be O(V^2), where V is the number of vertices.