History
While the ideas used in disjoint-set forests have long been familiar, Robert Tarjan was the first to prove the upper bound (and a restricted version of the lower bound) in terms of the inverse Ackermann function, in 1975. Until this time the best bound on the time per operation, proven by Hopcroft and Ullman, was O(log* n), the iterated logarithm of n, another slowly growing function (but not quite as slow as the inverse Ackermann function).
Tarjan and Van Leeuwen also developed one-pass Find algorithms that are more efficient in practice while retaining the same worst-case complexity.
In 2007, Sylvain Conchon and Jean-Christophe Filliâtre developed a persistent version of the disjoint-set forest data structure, allowing previous versions of the structure to be efficiently retained, and formalized its correctness using the proof assistant Coq.
Read more about this topic: Disjoint-set Data Structure
Famous quotes containing the word history:
“We have need of history in its entirety, not to fall back into it, but to see if we can escape from it.”
—José Ortega Y Gasset (1883–1955)
“Every literary critic believes he will outwit history and have the last word.”
—Mason Cooley (b. 1927)
“A people without history
Is not redeemed from time, for history is a pattern
Of timeless moments.”
—T.S. (Thomas Stearns)