# 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.

![M union-find operations on a set of N objects](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-eba16fb5cbdee8fe4d5f6c6fc929490bc650c98f%2Fimage%20\(17\).png?alt=media)