What is the time complexity of prim's algorithm?

Worst case O(E log V). Space complexity is O(V). Same cut property as Kruskal, applied to a different cut each round.

Prim's algorithm

medium

Grow a single tree by absorbing the cheapest edge leaving it. The only difference from Dijkstra is the priority: distance from the tree, not distance from the source.

Worst O(E log V)Space O(V)

Loading the prim's algorithm engine…

Where to go next

Kruskal's algorithm

medium

Cheapest edge first, skipping anything that closes a cycle.

Dijkstra's algorithm

medium

Settle the closest unvisited node, then relax its edges.

Binary heap

medium

An array pretending to be a tree.