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
- union-find — A data structure that tracks which items belong to the same group, supporting "find the group of x" and "merge the groups of x and y".
- amortised analysis — Measuring the average cost per operation over a long sequence of operations, so rare expensive steps are spread across many cheap ones.
Taught in
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers