3
$\begingroup$

I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function).

I understand why it is $O ( m \log^{\ast} ( n ) ) $ as it is proven on wikipedia.

So the question is, why is WQUPC $O( m \alpha (n) ) $? I would prefer a rigorous analysis, but an intuitive explanation would also be useful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.