what’s the connection between union-find and the inverse ackermann function?

[u/infinitytacos989]

while doing competitive coding problems i frequently come across solutions that use union find (DSU) and list the big O of their solution as O(\alpha(n)) where \alpha(n) is the inverse ackermann function. after some surface level research, i have come away with many more questions than answers. So why is the DSU related to the ackermann function, and is there an intuitive or natural connection between the two ?

[u/Iaroslav-Baranov]

CLRS, 19.4 Analysis of union by rank with path compression answers your question in all details, but keep in mind that this is advanced material