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:
“It is now time to stop and to ask ourselves the question which my last commanding officer, Admiral Hyman Rickover, asked me and every other young naval officer who serves or has served in an atomic submarine. For our Nation M for all of us M that question is, “Why not the best?””
—Jimmy Carter (James Earl Carter, Jr.)
“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)