Time Complexity
| Minimum edge weight data structure | Time complexity (total) |
|---|---|
| adjacency matrix, searching | O(V2) |
| binary heap and adjacency list | O((V + E) log V) = O(E log V) |
| Fibonacci heap and adjacency list | O(E + V log V) |
A simple implementation using an adjacency matrix graph representation and searching an array of weights to find the minimum weight edge to add requires O(V2) running time. Using a simple binary heap data structure and an adjacency list representation, Prim's algorithm can be shown to run in time O(E log V) where E is the number of edges and V is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(E + V log V), which is asymptotically faster when the graph is dense enough that E is ω(V).
Read more about this topic: Prim's Algorithm
Famous quotes containing the words time and/or complexity:
“Frequently also some fair-weather finery ripped off a vessel by a storm near the coast was nailed up against an outhouse. I saw fastened to a shed near the lighthouse a long new sign with the words “ANGLO SAXON” on it in large gilt letters, as if it were a useless part which the ship could afford to lose, or which the sailors had discharged at the same time with the pilot. But it interested somewhat as if it had been a part of the Argo, clipped off in passing through the Symplegades.”
—Henry David Thoreau (1817–1862)
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)