title: Is the complexity of prim's MST algorithm by adjacency matrix same as that of adjacency list with linear search?
body: <p>From my understanding, the use of heap helps by allowing constant cost for finding minimum value with the extra work of <code>log n</code> every time we change a value. Change in value can happen a maximum of <code>e</code> times. Time complexity is approximately <code>O(e) + O(e log n) = O(e log n)</code>.
  If it is a dense graph, <code>e = n^2</code>. </p>
  
  <p>But if we do the searching for minimum using linear search on the <code>value array</code>, we will get a complexity of <code>O(e) + O(n^2) = O(n^2)</code> which is better than <code>elog n</code> for dense graphs. This is similar to what we get from using a 2D array for graph representation in prim's MST algorithm.
  Then why do we use the 2D array representation at all for this specific algorithm?</p>
  
  <p><code>e</code> = number of edges.</p>
  
  <p><code>n</code> = number of nodes.</p>