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:
“People stress the violence. That’s the smallest part of it. Football is brutal only from a distance. In the middle of it there’s a calm, a tranquility. The players accept pain. There’s a sense of order even at the end of a running play with bodies stewn everywhere. When the systems interlock, there’s a satisfaction to the game that can’t be duplicated. There’s a harmony.”
—Don Delillo (b. 1926)
“At one time or another, almost every politician needs an honest man so badly that, like a ravenous wolf, he breaks into a sheep-fold: not to devour the ram he has stolen, however, but rather to conceal himself behind its wooly back.”
—Friedrich Nietzsche (1844–1900)