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:
“A young person is a person with nothing to learn
One who already knows that ice does not chill and fire does not burn . . .
It knows it can spend six hours in the sun on its first
day at the beach without ending up a skinless beet,
And it knows it can walk barefoot through the barn
without running a nail in its feet. . . .
Meanwhile psychologists grow rich
Writing that the young are ones’ should not
undermine the self-confidence of which.”
—Ogden Nash (1902–1971)
“If you can’t believe a little in what you see on the screen, it’s not worth wasting your time on cinema.”
—Serge Daney (1944–1992)