On the Expected Performance of Path Compression Algorithms
Andrew Chi-Chih Yao · SIAM Journal on Computing · 1985
We consider the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An $O(n)$ expected running time is proved for the execution of a random equivalence program in the Spanning Tree Model.