1 votes 1 votes 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 Algorithms ace-test-series + – Psnjit asked Jan 29, 2019 edited Mar 3, 2019 by I_am_winner Psnjit 322 views answer comment Share Follow See 1 comment See all 1 1 comment reply prashant jha 1 commented Jan 29, 2019 reply Follow Share 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)$ 1 votes 1 votes Please log in or register to add a comment.