alleryStart learning →Prim's algorithm with a Fibonacci heap runs in
AO(V²) on any graph
BO(E log E) like Kruskal exactly
CO(E + V log V)
DO(V³) on dense graphs
Answer & Solution
Correct answer: C. O(E + V log V)
Fibonacci heap gives O(1) amortised Decrease-Key and O(log V) Extract-Min.
**Total:** V Extract-Mins + E Decrease-Keys = O(V log V + E) = O(E + V log V).
On dense graphs (E = Θ(V²)) this is O(V²), beating Kruskal's O(E log V) = O(V² log V).
With a binary heap, Prim is O(E log V), matching Kruskal.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.