Ну, точно не зная, как выглядит конкретная реализация, сложно сказать, но если я правильно вспоминаю Prim, вам всегда нужно проверять ребра Θ (E) при определении MST.Если очередь приоритетов реализована в виде двоичной кучи (что является стандартным способом), то каждая «проверка» - это O (log V), поэтому всегда происходит наихудшее время выполнения O (E * log V).