Skip to main content
Lawrence Berkeley National Laboratory
A Simpler Proof Of The Average Case Complexity Of Union-Find With Path Compression
- Author(s): Wu, Kesheng
- Otoo, Ekow
- et al.
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.