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:
“The mere existence of an additional child or children in the family could signify Less. Less time alone with parents. Less attention for hurts and disappointments. Less approval for accomplishments. . . . No wonder children struggle so fiercely to be first or best. No wonder they mobilize all their energy to have more or most. Or better still, all.”
—Adele Faber (20th century)
“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)