Running Time
The algorithm can be shown to run in O(E log V (log log V)3) time, where E is the number of edges and V is the number of vertices. This bound is achieved as follows:
- sorting the edges by weight using a comparison sort in O(E log E) time
- E iterations of loop
- deleting in O(1) time
- connectivity checked in O(logV (log log V)3) time (Thorup 2000).
Equally, the running time can be considered O(E log E (log log E)3) because the largest E can be is V2. Remember that logV2 = 2 * logV, so 2 is a multiplicative constant that will be ignored in big-O notation.
Read more about this topic: Reverse-delete Algorithm
Famous quotes containing the words running and/or time:
“Of the thirty-six stratagems, the best is running away.”
—Chinese proverb.
“Our instructed vagrancy, which has hardly time to linger by the hedgerows, but runs away early to the tropics, and is at home with palms and banyans—which is nourished on books of travel, and stretches the theatre of its imagination to the Zambesi.”
—George Eliot [Mary Ann (or Marian)