Prim's Time Complexity

Prim's time complexity is $O(E \log V)$ with a binary heap, where $E$ is edges and $V$ is nodes. You push each edge once and pop at most $V$ times from the heap. With a Fibonacci heap, Prim runs in $O(E + V \log V)$, which is better for dense graphs.

But binary heaps are simpler and usually fast enough. For sparse graphs ($E \approx V$), Prim and Kruskal have similar performance. For dense graphs ($E \approx V^2$), Prim can be faster.

Space complexity is $O(V)$ for the data structures used.