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

ignougroup
Problem Detail: 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?

Asked By : ramgorur

Answered By : Massimo Cafaro

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 $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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13608