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:
“Animals used to provide a lowlife way to kill and get away with it, as they do still, but, more intriguingly, for some people they are an aperture through which wounds drain. The scapegoat of olden times, driven off for the bystanders’ sins, has become a tender thing, a running injury. There, running away ... is me: hurt it and you are hurting me.”
—Edward Hoagland (b. 1932)
“Gather ye rosebuds while ye may:
Old Time is still a-flying;
And this same flower that smiles today,
Tomorrow will be dying.”
—Robert Herrick (1591–1674)