Search code examples
mathgraphcomputer-scienceminimum-spanning-treeprims-algorithm

Prims Algorithm Total Running time!

"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 ?

Solution

  • 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