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:
“I am admonished in many ways that time is pushing me inexorably along. I am approaching the threshold of age; in 1977 I shall be 142. This is no time to be flitting about the earth. I must cease from the activities proper to youth and begin to take on the dignities and gravities and inertia proper to that season of honorable senility which is on its way.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“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)