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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top