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

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

  • Author(s): Wu, Kesheng
  • Otoo, Ekow
  • et al.
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.

Main Content
Current View