Amortized time per operation using disjoint sets

Question

I happened to read on Wikipedia that the amortized time per operation on a disjoint set (union two elements, find parent of a specific element) is O(a(n)), where a(n) is the inverse Ackermann function, which grows very fast.

Can anyone explain why this is true?

Answer 1

Well, the Wikipedia page has a citation. If you're that interested, check it out. If you're at college that should be easy, if not, just find a nearby college and use their library (they don't care if you're not a student).

Answer 2

Well, that would be rather hard to explain, because it isn't true. It's the non-inverse Ackermann function that grows like a rocket on steroids, the inverse Ackermann grows very slowly.

This gives you the theoretical background.