"Таким образом, общее время для алгоритма Прима равно O (V lg V + E lg V) = O (E lg V), что асимптотически совпадает с нашей реализацией алгоритма Крускала."
Из http://serverbob.3x.ro/IA/DDU0137.html
Но почему O (V lg V + E lg V) = O (E lg V) ??
Это потому, что E - это хотя бы V-1?
Потому что в обычном случае мы предполагаем, что E больше V. Поэтому, игнорируя члены более низкого порядка, мы получили E lg V
В частности, E может быть максимумом V ^ 2 в ориентированном графе. Если мы примем E = v ^ 2 (для учета наихудшего случая), E проглотит V.