Back to Search
Start Over
Top-Down Analysis of Path Compression.
- Source :
- SIAM Journal on Computing; 2005, Vol. 34 Issue 3, p515, 11p
- Publication Year :
- 2005
-
Abstract
- We present a new analysis of the worst-case cost of path compression, which is an operation that is used in various well-known "union-find" algorithms. In contrast to previous analyses which are essentially based on bottom-up approaches, our method proceeds top-down, yielding recurrence relations from which the various bounds arise naturally. In particular the famous quasi-linear bound involving the inverse Ackermann function can be derived without having to introduce the Ackermann function itself. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 34
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 16639495
- Full Text :
- https://doi.org/10.1137/S0097539703439088