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:
“Tattoo-shops, consulates, grim head-scarfed wives;
And out beyond its mortgaged half-built edges
Fast-shadowed wheat-fields, running high as hedges,
Isolate villages, where removed lives
Loneliness clarifies. Here silence stands
Like heat. Here leaves unnoticed thicken,
Hidden weeds flower....”
—Philip Larkin (1922–1986)
“A house means a family house, a place specially meant for putting children and men in so as to restrict their waywardness and distract them from the longing for adventure and escape they’ve had since time began.”
—Marguerite Duras (b. 1914)