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 may pretend that we’re basically moral people who make mistakes, but the whole of history proves otherwise.”
—Terry Hands (b. 1941)
“The steps toward the emancipation of women are first intellectual, then industrial, lastly legal and political. Great strides in the first two of these stages already have been made of millions of women who do not yet perceive that it is surely carrying them towards the last.”
—Ellen Battelle Dietrick, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4, ch. 13, by Susan B. Anthony and Ida Husted Harper (1902)
“There is a constant in the average American imagination and taste, for which the past must be preserved and celebrated in full-scale authentic copy; a philosophy of immortality as duplication. It dominates the relation with the self, with the past, not infrequently with the present, always with History and, even, with the European tradition.”
—Umberto Eco (b. 1932)