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?
MST: Prim's algorithm complexity, why not $O(EV \lg V)$?
algorithms;algorithm analysis;spanning trees
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-KEYs. 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 $E$ is at most $V^2$, then $\log E$ is at most $2 \log V$. 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. 