Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$? 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.


Initialization of key and predecessor + making a binary heap = $O(|V|)$
EXTRACT-MIN operation = $O(|V|lg|V|)$
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.
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) &lt; 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.