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.


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.