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