Kruskal vs. Prim on dense vs. sparse graphs

Kruskal's algorithm sorts all E edges (O(E log E)) then processes them with union-find, roughly O(E) more, giving O(E log E) = O(E log V) overall (since E ≤ V^2 implies log E = O(log V)). Prim's algorithm with a Fibonacci-heap-backed priority queue runs in O(E + V log V). For a dense graph with E = Θ(V^2), which is asymptotically faster, and why?

23 of 46 in Data Structures & Algorithms