October 26, 2023
October 26, 2023
October 26, 2023
###### Greedy-approach
October 26, 2023
 Question 2

Which of the following statement is false about Prim’s algorithm?

 A Initially the roots key and nodes are initialized to zero B It may use binomial max heap to represent the primary queue C The complexity is O(E log V) using binary heap D The time complexity is O(E + V log V) using Fibonacci Heap
Question 2 Explanation:
S1 is false because only the root key is initialized to zero so that it can be picked first and the rest nodes are initialized to infinity.
The time complexity of Prim’s algorithm using binary heap is O( E log V).

And the time complexity of prim’s algorithm using Fibonacci heap is O(E + V log V) because the decrease key operation takes O(1) time in Fibonacci heap whereas using binary heap it takes O(log n) time.
Question 2 Explanation:
S1 is false because only the root key is initialized to zero so that it can be picked first and the rest nodes are initialized to infinity.
The time complexity of Prim’s algorithm using binary heap is O( E log V).

And the time complexity of prim’s algorithm using Fibonacci heap is O(E + V log V) because the decrease key operation takes O(1) time in Fibonacci heap whereas using binary heap it takes O(log n) time.