Question

Time complexity of Prim’s algorithm is _________

(a) O((V+E)logV)

(b) O(E+V)

(c) O(E)

(d) O(V+1)

I have been asked this question by my school teacher while I was bunking the class.

Question is from Spanning Trees in division Trees of Discrete Mathematics

Answer 1

Correct choice is (a) O((V+E)logV)

To elaborate: In Prim’s Algorithm, we will start with an arbitrary node (take any point to start) and mark it. In each iteration, a new vertex is marked that is adjacent to the one that we have already marked. Each vertex is inserted in the priority queue only once and insertion in priority queue take logarithmic time. Hence, the time complexity of Prim’s Algorithm is O((V+E)logV).