Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?

Question

In the CLRS, time complexity of Prim's algorithm is $O(|V|lg|V|+|E|lg|V|)=O(|E|lg|V|)$.

But, for my understanding, Prim's algorithm iterates $|E|$ times for DECREASE-KEY operation which takes $O(lg|V|)$ times and it leads to $O(|E|lg|V|)$.

So, it iterates $|V|$ times then, I think $O(|E||V|lg|V|)$ is right because whole time complexity is like below.

1. Initialization of key and predecessor + making a binary heap = $O(|V|)$
2. EXTRACT-MIN operation = $O(|V|lg|V|)$
3. DECREASE-KEY operation is iterated for $|V|$ times = $O(|E||V|lg|V|)$

Consequently, $O(|V|+|V|lg|V|+|E||V|lg|V|)=O(|E||V|lg|V|)$.
Why is it $O(|E|lg|V|)$?

---

From 2 answers, first while loop iterates $|V|$ times and $DECREASE-KEY$ operation iterates $|E|$ times and time complexity of that operation is $O(lg|V|)$ because min heap has to be reconstructed.

From this, I got a $O(|V||E|lg|V|)$ because for loop is in while loop. What your answers are saying is that I don't know $DECREASE-KEY$ operation iterates $|E|$ times, but I know that.

Answer 1

DECREASE-KEY is called at most $2|E|$ times: it is called at most twice per edge (i.e., for each edge $(u,v)$, we call DECREASE-KEY on $v$ when $u$ leaves the queue, and DECREASE-KEY on $u$ when $v$ leaves the queue). DECREASE-KEY costs $O(\log |V|)$ time per call to DECREASE-KEY.

Therefore, the total cost from all of the DECREASE-KEYs is $O(|E| \log |V|)$, not $O(|E| |V| \log |V|)$.

I can see why you might be thinking $O(|E| |V| \log |V|)$: you might be thinking that the outer loop can iterate $|V|$ times, and you might be thinking that the inner loop might iterate up to $|E|$ times, for a total of $|E| |V|$ calls to DECREASE-KEY. But that is too conversative. The number of times the inner loop iterates is not $|E|$, but rather the degree of the current node. The sum of the degrees of the nodes is $2|E|$, not $|E| |V|$. (Why is the sum of the degrees $2|E|$? It's because each edge contributes twice to this sum, once for each endpoint of the edge. See Christofides algorithm: why must an MST have even number of odd-degree vertices?.)

Answer 2

The pseudocode for Prim's algorithm, as stated in CLRS, is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)

The loop in line 6 will execute exactly $|V|$ times, since $Q$ starts with $|V|$ elements and we remove one each iteration. For each node $u$, the loop in line 8 will execute $\text{deg}(u)$ times, so the DECREASE-KEY operation (lines 10 and 11) will execute at most $\text{deg}(u)$ times.

In total, the loop in line 8 will be executed $2|E| = \sum_{u \in G.V} \deg(u)$ times, and DECREASE-KEY $O(|E|)$ times.

---

I would suggest you to grab a piece of paper, draw a graph, and run the algorithm on it while counting how many times you do the DECREASE-KEY operation.