Prims Algorithm Total Running time!

Question

"Thus, the total time for Prim's algorithm is O(V lg V + E lg V) = O(E lg V), which is asymptotically the same as for our implementation of Kruskal's algorithm."

From http://serverbob.3x.ro/IA/DDU0137.html

But why is O(V lg V + E lg V) = O(E lg V) ??

Is it because E is at least V-1 ?

Abdul Samad · Accepted Answer · 2011-06-14 23:01:57Z

3

Because in the normal case we assume that E is larger than V. So by ignoring the lower order terms we got E lg V

answered Jun 14, 2011 at 23:01

Abdul Samad

5,99817 gold badges60 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user1114 · Accepted Answer · 2012-04-15 06:08:09Z

1

Specifically, E can be a maximum of V^2 in a directed graph. If we assume E = v^2 (to account for worst case), E swallows V.

answered Apr 15, 2012 at 6:08

user1114

1,1892 gold badges18 silver badges35 bronze badges

Collectives™ on Stack Overflow

Prims Algorithm Total Running time!

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related