A Simpler Proof Of The Average Case Complexity Of Union-Find With
Path Compression
Kesheng Wu and Ekow Otoo
2005
Abstract
We present a modified union-find algorithm that represent the data in an
array rather than the commonly used pointer-based data structures, and a
simpler proof that the average case complexity of the union-find
algorithm is linear.
