Inverse Ackermann function

The inverse Ackermann function \(\alpha(N)\) is defined using recursion on a hierarchy of functions that starts with \(\alpha_1(n)=\lfloor\frac{n}{2}\rfloor\), and has been demonstrated to have slow-growing behavior analogous to the fast-growing behavior of the Ackermann function. It is notable on its own for its use in computational complexity theory; there are algorithms, such as one for the Union-Find problem, known to have time complexity \(O(g(n))\) where \(g\) is linear in \(\alpha_n(n)\) (or otherwise involving the function). \(\alpha\) is so slow-growing that such algorithms practically run in constant time.
==Sources==
Category:Functions