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:
“Time isnt so important.... We can say that time is behind us, that weve had years together.... I can tell you about a thousand wonderful hours weve spent together because I feel we would have, inevitably. And theres not that much difference between the future and the past.”
—Kurt Neumann (19061958)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put intelephonic, technological and relationalto alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)