title: Prim's Algorithm Time Complexity
body: <p>I was looking at the <a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm" rel="noreferrer">Wikipedia entry</a> for Prim's algorithm and I noticed that its time complexity with an adjacency matrix is O(V^2) and its time complexity with a heap and adjacency list is O(E lg(V)) where E is the number of edges and V is the number of vertices in the graph.</p>
  
  <p>Since Prim's algorithm is used in denser graphs, E can approach V^2, but when it does, the time complexity with a heap becomes O(V^2 lg(V)) which is greater than O(V^2).  Obviously, a heap will improve performance over just searching the array, but the time complexity says otherwise.</p>
  
  <p>How does the algorithm actually slow down with an improvement?</p>