retagged by
1,130 views
0 votes
0 votes
What is the time complexity of Prim algorithm without using min heap?
retagged by

1 Answer

0 votes
0 votes

Use min heap :

                      Extract_min -> O(V log V)

                      Decrease_key -> O(E logV)

                     Build_heap -> O(E)

  TC = O(V logV + E logV + E) == O(E logE)

Use Fibonacci_heap ::

According Fibonacci heap perform Decrease_key in "Constent Time"

                          TC = O(V logV + E)

https://stackoverflow.com/questions/4825518/how-to-implement-prims-algorithm-with-a-fibonacci-heap

http://www.cs.northwestern.edu/~agupta/_projects/algorithms/Fibonacci%20Heaps/Doc/Design%20Document%20%231.pdf

             

Related questions

3 votes
3 votes
1 answer
4
pC asked Sep 22, 2017
2,508 views
Explain Prims AlgorithmAnalysis Of Time ComplexityHow does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$