# MST: Prim's algorithm complexity, why not $O(EV \lg V)$?

According to CLRS, the Prim's algorithms is implemented as below --

$\mathtt{\text{MST-PRIM}}(G,w,r)$

• for each $u \in V[G]$ do
• $\mathtt{\text{key}}[u] \leftarrow \infty$
• $\pi[u] \leftarrow \mathtt{\text{NIL}}$
• $\mathtt{\text{key}}[r] \leftarrow 0$
• $Q \leftarrow V[G]$
• while $Q \ne \emptyset$ do // ... $O(V)$
• $u$ $\leftarrow$ $\mathtt{\text{EXTRACT-MIN}}(u)$ // ... $O(\lg V)$
• for each $v \in \mathtt{\text{adj}}[u]$ do // ... $O(E)$
• if $v \in Q$ and $w(u,v) \gt \mathtt{\text{key}}[v]$
• then $\pi[v] \leftarrow u$
• $\mathtt{\text{key}} \leftarrow w(u,v)$ // $\mathtt{\text{DECREASE-KEY}}$ ... $O(\lg V)$

The book says the total complexity is $O(V \lg V + E \lg V) \approx O(E \lg V)$. However, what I understood is that the inner for loop with the DECREASE-KEY operation will cost $O(E \lg V)$, and the outer while loop encloses both the EXTRACT-MIN and the inner for loop, so the total complexity should be $O(V (\lg V + E \lg V)) = O(V \lg V + EV \lg V) \approx O(EV \lg V)$.

Why the complexity analysis is not performed as such? and What is wrong with my formulation?

The complexity is derived as follows. The initialization phase costs $$O(V)$$. The $$while$$ loop is executed $$\left| V \right|$$ times. The $$for$$ loop nested within the $$while$$ loop is executed $$degree(u)$$ times. Finally, the handshaking lemma implies that there are $$\Theta(E)$$ implicit DECREASE-KEY’s. Therefore, the complexity is: $$\Theta(V)* T_{EXTRACT-MIN} + \Theta(E) * T_{DECREASE-KEY}$$.
The actual complexity depends on the data structure actually used in the algorithm. Using an array, $$T_{EXTRACT-MIN} = O(V), T_{DECREASE-KEY} = O(1)$$, complexity is $$O(V^2)$$ in the worst case.
Using a binary heap, $$T_{EXTRACT-MIN} = O(\log V), T_{DECREASE-KEY} = O(\log V)$$, complexity is $$O(E \log V)$$ in the worst case. Here is why: since the graph is connected, then $$\left| E \right| \ge \left| V \right| - 1$$, and $$E$$ is at most $$V^2$$ (worst case, for a dense graph) . Probably, you missed this point.
Using a Fibonacci Heap, $$T_{EXTRACT-MIN} = O(\log V)$$ amortized, $$T_{DECREASE-KEY} = O(1)$$ amortized, complexity is $$O(E + V \log V)$$ in the worst case.
Your idea seems correct. Let's take the complexity as $V(\lg v + E\lg v)$. Then notice that in the inner for loop, we are actually going through all the vertices, and not the edges, so let's modify a little to $V(\lg v + V\lg v)$, which means $V\lg v + V^2\lg v$. But for worst case analysis (dense graphs), $V^2$ is roughly equal to number of edges, $E$, giving $V\lg v + E\lg v = (V+E)\lg v$ but since $V \ll E$, hence $E\lg v$.
• What's $v$? A typo for $V$? – David Richerby Mar 7 '16 at 16:08