Prim's Algorithm - Time Complexity

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 isn’t so important.... We can say that time is behind us, that we’ve had years together.... I can tell you about a thousand wonderful hours we’ve spent together because I feel we would have, inevitably. And there’s not that much difference between the future and the past.
    Kurt Neumann (1906–1958)

    The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to 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)