The running time of Kruskal's algorithm with Union-Find is
AO(V²) regardless of E
BO(V³) regardless of E
CO(V × E) brute force
DO(E log V) using sort
Answer & Solution
Correct answer: D. O(E log V) using sort
Sorting the E edges costs O(E log E) = O(E log V) since E ≤ V². The Union-Find operations are O(α(V)) per call, essentially O(1) amortised over the E edges. Sort dominates. O(V²) or O(VE) describe naive approaches without sorting or Union-Find.
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