Friday, July 30, 2004

Path compression...

The main takeaway from the Seidel-Sharir paper refining the analysis for union-find, as explained to me by Adam Buchsbaum (who is still walking the corridors in amazement):

If path compression takes linear time, then it takes α(n) (amortized) time.

Truly amazing. Worth reading just for that...

No comments:

Post a Comment

Disqus for The Geomblog