inverse Ackermann function

A function that grows so slowly it is at most 4 for any input size that could ever exist, used to express union-find's amortised cost.

In more detail

It is the inverse of the Ackermann function, which grows faster than any tower of exponents. Union-find with path compression and union by rank costs O(α(n)) amortised per operation, which in practice is a constant.

Related terms

Taught in

References