CODEWITHSUNDEEP
algorithmcomplexity-theorybig-oprims-algorithm
rajya vardhan
rajya vardhan

Reputation: 1131

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

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:

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?

Upvotes: 4

Views: 4536

Answers (2)

yairchu
yairchu

Reputation: 24814

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

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

Upvotes: 7

Nick Dandoulakis
Nick Dandoulakis

Reputation: 43160

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.

Upvotes: 1

Related Questions