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.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for