The expected linearity of a simple equivalence algorithm

AbstractThe average time needed to form unions of disjoint equivalence classes, using an algorithm suggested by Aho, Hopcroft, and Ullman, is shown to be linear in the total number of elements, thereby establishing a conjecture of Yao. The analytic methods used to prove this result are of interest in themselves, as they are based on extensions of Stepanov's approach to the study of random graphs. Several refinements of Yao's analyses of related algorithms are also presented