Ace Test Series: Algorithms - Prims Algorithm Time Complexity

Question

Time complexity of Prim's algorithm for computing minimum cost spanning tree for a complete graph with n vertices and e edges using Heap data structure is-

1. (n+e)*log^2n

2. n^2

3. n^2*logn

4. n*logn

Comments

Time complexity of Prim's algorithm is :-

$O(|e+n|(Log_{2}n))$ with the use of binary min heap.

Since $G$ is a complete graph , $e = \frac{n(n-1)}{2}$ , where n is the number of vertices

Thus complexity will be =$O(| \frac{n(n-1)}{2}+n|(Log_{2}n)) = O(n^{2}Log_{2}n)$