How Prim's algorithm time complexity is ElogV using Priority Q?

Question

Pseudo code which I used:

for all V vertices: visited[n]=0

pick any vertex r from graph and set visited[r]=1

For all edges e incident to r
PQ.insert()

while(PQ is not empty)//line 1
  f=PQ.min()//f(r,s) is such that visited[s]=0
  for all edges e(s,t) incident to s//line 2
     if(visited[t]==0)
        PQ.insert(e);//line 3
     else
        PQ.delete(e);//line 4
  visited[s]=1;
end while;

According to my understanding:

• line 1 : executes V-1 times.
• Line 2 : Sum of Degree of all the vertices times…..that is 2E times

For each line 2: Line 3 and line 4 take log E time because we’re adding/deleting all the edges to/from the PQ one by one.

So total time= V-1+2E.logE = E.log E

But the book says it is E.logV, could you explain why that is?

Answer 1

O(log(V)) and O(log(E)) are the same.

• E is at most V².
• log(V²) = 2*log(V)
• which is an O(log(V))

Answer 2

for all edges e(s,t) incident to s

How many edges a node s can have at most?
V-1 at most. So, PQ operations have O(logV) time complexity.