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:
“What was any art but an effort to make a sheath, a mould in which to imprison for a moment the shining, elusive element which is life itself—life hurrying past us and running away, too strong to stop, too sweet to lose?”
—Willa Cather (1873–1947)
“They do not live in the world,
Are not in time and space.
From birth to death hurled
No word do they have, not one
To plant a foot upon,
Were never in any place.”
—Edwin Muir (1887–1959)