The Inverse Ackermann Bound

The Ackermann Function

The Ackermann function $A_k(j)$ is defined recursively:

$A_0(j) = j + 1$

$A_k(j) = A_{k-1}^{(j+1)}(j) \quad \text{for } k \ge 1$

where $f^{(m)}(x)$ denotes the $m$-fold iterated application of $f$. That is:

$f^{(0)}(x) = x, \quad f^{(m+1)}(x) = f(f^{(m)}(x))$

Concrete Values

$k$	$A_k(1)$	Growth
0	$A_0(1) = 2$	Linear
1	$A_1(1) = A_0^{(2)}(1) = A_0(A_0(1)) = A_0(2) = 3$	Small
2	$A_2(1) = A_1^{(2)}(1) = A_1(A_1(1)) = A_1(3)$	Growing
	$A_1(3) = A_0^{(4)}(3) = 3+4 = 7$, so $A_2(1) = 7$
3	$A_3(1) = A_2^{(2)}(1) = A_2(A_2(1)) = A_2(7)$	Exploding
	$A_2(7) = 2^{7+3} - 3 = 1021$, so $A_3(1) = 2047$
4	$A_4(1) \approx 2^{2^{2^{65536}}}$	Astronomically large

The function grows incomprehensibly fast. $A_4(1)$ is already far larger than the number of atoms in the observable universe.

The Inverse Ackermann Function

The inverse Ackermann function $\alpha(n)$ is defined as:

$\alpha(n) = \min \{ k \mid A_k(1) \ge n \}$

In words: the smallest $k$ such that the Ackermann function with parameter $k$ and argument 1 reaches or exceeds $n$.

Values of $\alpha(n)$

$n$	$\alpha(n)$
$0, 1, 2$	$0$
$3$	$1$
$4 \ldots 7$	$2$
$8 \ldots 2047$	$3$
$2048 \ldots A_4(1)-1$	$4$

For any $n$ that could ever arise in practice (even $n = 10^{80}$, the estimated number of atoms in the universe), $\alpha(n) \le 4$. The function grows so slowly that it is effectively constant.

The Union-Find Complexity Result

Theorem (Tarjan, 1975): A sequence of $m$ MakeSet, Union, and Find operations, of which $n$ are MakeSet, on a disjoint-set forest with union by rank and path compression takes $O(m \cdot \alpha(n))$ time in the worst case.

Since $\alpha(n) \le 4$ for all practical $n$, this is effectively $O(m)$ — linear time.

Proof Sketch (Beyond Exam Scope)

The full proof partitions ranks into blocks based on how many times $\log^*$ must be applied to bring the rank below a threshold. Each node is assigned a “level” in this hierarchy. Path compression is charged to nodes moving between levels, and the potential function captures that each node can only move a bounded number of levels (at most $\alpha(n)$ times). The full argument appears in CLRS Chapter 21.

What You Need to Know for the Exam

1. The result: $m$ operations on $n$ elements take $O(m \cdot \alpha(n))$ time with union by rank and path compression.
2. The definition: $\alpha(n) = \min\{k : A_k(1) \ge n\}$.
3. The practical bound: $\alpha(n) \le 4$ for any $n$ less than $A_4(1)$, which covers all realistic input sizes.
4. The two heuristic names: Union by rank and path compression.
5. How Kruskal uses it: Sorting dominates; the union-find operations contribute $O(E \cdot \alpha(V))$, so overall $O(E \log V)$.

You are NOT expected to reproduce the full Tarjan proof. You should be able to state the result, define $\alpha(n)$, compute small values, and explain why the bound is effectively constant.

Worked Example: $\alpha(n)$ Computation

Compute $\alpha(100)$:

• $A_0(1) = 2$, not $\ge 100$
• $A_1(1) = 3$, not $\ge 100$
• $A_2(1) = 7$, not $\ge 100$
• $A_3(1) = 2047 \ge 100$

Smallest $k$ is 3, so $\alpha(100) = 3$.

Compute $\alpha(10^6)$:

• $A_3(1) = 2047$, not $\ge 10^6$
• $A_4(1)$ is enormous, $\ge 10^6$

So $\alpha(10^6) = 4$.

Summary

Concept	Detail
Ackermann function	$A_0(j) = j+1$, $A_k(j) = A_{k-1}^{(j+1)}(j)$
Inverse Ackermann	$\alpha(n) = \min\{k : A_k(1) \ge n\}$
$\alpha(n)$ values	$n \le 2 \Rightarrow 0$, $n=3 \Rightarrow 1$, $n=4..7 \Rightarrow 2$, $n=8..2047 \Rightarrow 3$, $n \ge 2048 \Rightarrow 4$
Union-find bound	$O(m \cdot \alpha(n))$ with both heuristics
Practical constant	$\alpha(n) \le 4$ for all realistic $n$
Exam scope	Result + definition + small values; not full proof
Past questions	Ex. sheet 6 q.13; Tripos questions on Kruskal analysis