> For the complete documentation index, see [llms.txt](https://blog.sunilgudivada.dev/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.sunilgudivada.dev/notebook/data-structures-and-algorithms/topics/union-find-data-structure/amortized-analysis.md).

# 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](/files/lsUdGGkw2qUKeN0fuQ3v)