edited by
2,112 views
1 votes
1 votes
Which one of following statement is false about prim's algorithm?

a) It use a running time of O(Elog2V) using binary heap

b) It may use a binomial max-heap to represent the priority queue.

c) A fibonacci heap imlementation require O(E+V log2V)

d) Initially all keys of nodes in priority queue are set to infinity . The root's key is set to 0.
edited by

2 Answers

3 votes
3 votes
answer should (b)

prims algo can be implemented using  without heap (O(n^2)) , with  binary heap ( O(VlogV+ElogV+O(E)  = O(ElogV)) and fibonacci heap (O(VlogV+E)) so option a,c are correct .

for option d  this is initial step for implementation

option b which is wrong ...https://en.wikipedia.org/wiki/Binomial_heap

Related questions

3 votes
3 votes
1 answer
1
pC asked Sep 22, 2017
2,506 views
Explain Prims AlgorithmAnalysis Of Time ComplexityHow does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
0 votes
0 votes
1 answer
2
anonymous asked Jun 26, 2016
640 views
2 votes
2 votes
2 answers
3
techbrk3 asked Nov 16, 2017
495 views
(a,b),(b,c),(a,d),(e,f),(d,g),(c,e)(g,f),(f,c),(g,d),(c,e),(d,b),(d,a)(c,f),(c,e),(e,d),(a,b),(d,g),(b,c)None of the above
1 votes
1 votes
0 answers
4
just_bhavana asked Oct 30, 2017
817 views
Assuming that the graph can contain repeated edge weights, we have a single tree at any instance when applying Prim's algorithm.Justify this statement.