Prims Algorithm Total Running time!
-
28-10-2019 - |
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 ?
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
OTHER TIPS
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.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow