Amortized Analysis

WQUPC - Weighted quick-union with path compression: amortized analysis

Linear-time algorithm for M union-find ops on N objects?

Cost within constant factor of reading in the data. In theory, WQUPC is not quite linear. In practice, WQUPC is linear.