Time and Space Complexity

Time Complexity:

• The edge-scan version here is O(V * E): V-1 rounds, each scanning all E edges. With a binary heap and adjacency lists, Prim runs in O((V + E) log V).

Space Complexity:

• O(V) for the inTree array (plus the input edges).

Summary:

• Prim grows one tree, always adding the cheapest edge leaving it, until every vertex is included.
• It produces the same minimum total weight as Kruskal, using a different strategy.