4.0.1 Satz von Tarjan
Der Aufwand um m-mal Union/Find durchzuführen beträgt
m
·
(
m
,
n
) , wobei
die inverse Ackermannfunktion darstellt, eine stark steigende Funktion.
Das bedeutet, daß Union/Find in fast konstanter Zeit abläuft.