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:
“Miss U.S.A. is in the same graveyard that [Amanda Jones] the twelve-year-old is. Where the sixteen-year-old is. All the past selves. There comes a time when you have to bury those selves because you’ve grown into another one.”
—Amanda Theodosia Jones, U.S. beauty contest winner, Miss U.S.A., 1973. As quoted under the pseudonym “Emma Wright” in American Dreams, Prologue, by Studs Terkel (1980)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)