Why do Kruskal and Prim MST algorithms have different runtimes for sparse and dense graphs?

Question

I am trying to understand why Prim and Kruskal have different time complexities when it comes to sparse and dense graphs. After using a couple of applets that demonstrate how each works, I am still left a little confused about how the density of the graph affects the algorithms. I hope someone could give me a nudge in the right direction.

Answer 1

Wikipedia gives the complexity of these algorithms in terms of E, the number of edges, and V, the number of vertices, which is a good practice because it lets you do exactly this sort of analysis.

Kruskal's algorithm is O(E log V). Prim's complexity depends on which data structure you use for it. Using an adjacency matrix, it's O(V²).

Now if you plug in V² for E, behold you get the complexities that you cited in your comment for dense graphs, and if you plug in V for E, lo you get the sparse ones.

Why do we plug in V² for a dense graph? Well even in the densest possible graph you can't have as many as V² edges, so clearly E = O(V²).

Why do we plug in V for a sparse graph? Well, you have to define what you mean by sparse, but suppose we call a graph sparse if each vertex has no more than five edges. I would say such graphs are pretty sparse: once you get up into the thousands of vertices, the adjacency matrix would be mostly empty space. That would mean that for sparse graphs, E ≤ 5 V, so E = O(V).