Understanding the Inverse Ackermann Function
Raimund Seidel · 2006
The so-called inverse Ackermann function is an exceedingly slowly growing function that arises in bounds for a number of computational/combinatorial problems. The proofs of those bounds are usually tedious, proceed in a bottom-up fashion, and provide little (if any) intuition in the nature of the bound. In my talk I will describe a top-down approach that is rather simple and leads naturally to such inverse Ackermann function bounds (without ever having to talk about the Ackermann function itself). The most striking example will be so-called path compression, which arises in algorithms for the union-find problem. This is one of the basic problems in algorithmics. It is distinguished by the fact that it is typically the only basic problem in intermediate level algorithms courses for which fast solutions are taught but not analyzed.