8
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What's $v$? A typo for $V$? $\endgroup$ – David Richerby Mar 7 '16 at 16:08
  • $\begingroup$ Actually, I don't understand this at all. What does it mean to say "Let's take the complexity as [expression 1]" and then "modify a little to [expression 2]"? You can't just assume the running time is one thing and then change it to something else. $\endgroup$ – David Richerby Mar 7 '16 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.