Skip to main content
Open Access Publications from the University of California

A Simpler Proof Of The Average Case Complexity Of Union-Find With Path Compression


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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View