Operating-Systems
October 26, 2023Greedy-approach
October 26, 2023Greedy-approach
|
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