the inverse-Ackermann bound
/ AK-er-man /
The Ackermann function is a famous example of a function that grows almost unimaginably fast — faster than any tower of exponentials — by nesting recursion inside recursion. Its inverse, written alpha(n), therefore grows almost unimaginably SLOWLY: it is the number of times you would have to apply a wildly fast-growing operation to climb from a small number up to n. For every n you could ever store in a computer — indeed for n far larger than the number of atoms in the universe — alpha(n) is at most 4 or 5. It is not technically a constant, but it might as well be.
This function is the exact amortized cost per operation of union-find when you use BOTH path compression and union by rank. Tarjan proved that a sequence of m operations on n elements runs in O(m * alpha(n)) total time, so each operation amortizes to O(alpha(n)). The proof is one of the most intricate in basic algorithms: it assigns nodes to 'levels' based on how their rank compares with their parent's rank, and charges the work of each Find either to the operation itself or to nodes that get promoted to higher levels, showing each node can only be charged a bounded number of times per level and there are only alpha(n) levels. The upshot is that the self-improving structure pays back its rare expensive operations so thoroughly that the average is essentially constant. There is also a matching lower bound: no pointer-based union-find can beat alpha(n) amortized, so this is not just the best known bound, it is provably optimal.
The inverse-Ackermann bound is why union-find is treated as 'effectively constant time' in practice — Kruskal's MST, connectivity queries, and dozens of other algorithms rely on it. The honest framing: alpha(n) is genuinely not O(1) as a function (it does tend to infinity, just glacially), and the bound is amortized, so an individual Find can still take longer than alpha(n) when it flattens a long path. But for any real input the distinction between alpha(n) and a constant is academic — you will never see alpha(n) exceed 5.
To grasp how slowly alpha grows: a related slow function, the iterated logarithm log*(n), needs about 5 applications of log to reduce 2^65536 to below 1, and alpha(n) grows even more slowly than log*(n). So a million operations on a million elements amortize to roughly 4 or 5 units each — indistinguishable from constant in any real program.
alpha(n) is at most 4 or 5 for any n you could ever encounter — effectively constant, though not literally O(1).
alpha(n) is not literally a constant — it does grow to infinity, and the bound is amortized. But it is provably optimal for pointer-based union-find, and on real inputs it never exceeds about 5, so treating it as constant is fair in practice though wrong in the strict limit.