Complexity of Dijkstra's and Prim's about interviews HOT 4 OPEN

Even I think so. Kruskal's Minimum Spanning Tree can be implemented in O(|E| log|V|) using Union-Find Data Structure and Prim's MST also has same running time. I have read somewhere that both have same running time.

from interviews.

Well, however, in my understanding, Kruskal's algorithm usually runs in O(|E| log |E|). It is different from Prim's algorithm which runs in O(|E| log |V|. It is nothing wrong actually.

from interviews.

O(|E| log |E|) is actually just O(|E| log |V|)
The max value of E is V^2 (in a fully connected graph), so at most log |E| produce 2 log |V|, which the coefficient is ignored in Big-O, so they are actually the same.

from interviews.

Yeah, that's what I meant @ip4368

from interviews.