1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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?.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I edited plz see and answer $\endgroup$ – molamola May 22 '18 at 22:59
  • $\begingroup$ @haram, OK! See my edited answer. $\endgroup$ – D.W. May 23 '18 at 0:18
  • $\begingroup$ Ok, I got it, you mean iteration time is the sum of degrees because we compute degrees for each vertex? Then, $O(2|E|lg|V|)=O(|E|lg|V|)$? Am I right? $\endgroup$ – molamola May 23 '18 at 1:48
  • $\begingroup$ @haram, yes, that's right. $\endgroup$ – D.W. May 23 '18 at 5:52
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I edited plz see and answer $\endgroup$ – molamola May 22 '18 at 22:59

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.