OperatingSystems
October 26, 2023Greedyapproach
October 26, 2023Greedyapproach
Question 2

Which of the following statement is false about Prim’s algorithm?
Initially the roots key and nodes are initialized to zero


It may use binomial max heap to represent the primary queue


The complexity is O(E log V) using binary heap


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.
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.
Correct Answer: A
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.
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.
Subscribe
Login
0 Comments