(Updated June 2009)
The inverse Ackermann function is an
extremely slowgrowing function which occasionally turns up in computer science and mathematics. The function is denoted
α(n) (alpha of
n).
This function is most wellknown in connection with the UnionFind problem: The optimal algorithm for the UnionFind problem runs in time O(mα(n) + n), where n is the number of elements and m is the total number of Union and Find operations performed. (See Cormen et al., Introduction to Algorithms, Second Edition, Chapter 21, MIT Press, 2001.) (A more precise bound is O(mα(m, n) + n), with a twoparameter version of the inverse Ackermann function, which we will explain below.)
The inverse Ackermann function also arises in computational geometry. For example, the maximum complexity of the lower envelope of n segments in the plane is Θ(nα(n)). (See J. Matoušek, Lectures on Discrete Geometry, Chapter 7, SpringerVerlag, New York, 2002.)
For some reason the inverse Ackermann function gets much less attention than it deserves. This is probably due to the perception that just defining α(n) is complicated, never mind working with it.
It may come as a surprise, then, that there is a very simple and elegant way to define the inverse Ackermann function and derive its asymptotic properties. Moreover, there is no need to make any mention of A, the very quicklygrowing Ackermann function.
In other words, dealing with α(n) does not have to be painful!
There are several different versions of the inverse Ackermann function in the literature. In fact, usually one needs to define a specific version of the function for each application. However, at the end of the day, all definitions yield equivalent asymptotic behavior; namely, we have α(n) − α'(n) = O(1) for any two versions α and α'. Thus, it is convenient to have a canonical definition of α(n), which we would like to be as simple and elegant as possible.
The inverse Ackermann hierarchy is a sequence of functions α_{k}(n), for k = 1, 2, 3, ..., where each function in the hierarchy grows much more slowly than the previous one.
Let [] denote the ceiling function (rounding up to the nearest integer). Then the inverse Ackermann hierarchy is defined as follows. We first let
α_{1}(n) = [n / 2].
Then, for each k ≥ 2, we let α_{k}(n) be the number of times we have to apply the function α_{k−1}, starting from n, until we reach 1. Formally, for k ≥ 2, we let
α_{k}(1) = 0; α_{k}(n) = 1 + α_{k}(α_{k−1}(n)), n ≥ 2.
The following table shows the first values of α_{k}(n):
n 
= 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
... 
n

α_{1}(n) 
= 
1 
1 
2 
2 
3 
3 
4 
4 
5 
5 
6 
6 
7 
7 
8 
8 
9 
9 
10 
10 
11 
11 
12 
12 
13 
... 
[n / 2]

α_{2}(n) 
= 
0 
1 
2 
2 
3 
3 
3 
3 
4 
4 
4 
4 
4 
4 
4 
4 
5 
5 
5 
5 
5 
5 
5 
5 
5 
... 
[log_{2} n]

α_{3}(n) 
= 
0 
1 
2 
2 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
4 
4 
4 
4 
4 
4 
4 
4 
4 
... 
log* n

α_{4}(n) 
= 
0 
1 
2 
2 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
3 
...

...

We have α_{2}(n) = [log_{2} n], and α_{3}(n) is the iterated logarithm function, denoted log* n.
Claim 1: If n ≥ 4 then α_{k}(n) ≤ n − 2.
Proof: By induction on k. The case k = 1 is clear. So assume k ≥ 2.
If n = 4, then α_{k}(n) = 2; and if n = 5 or 6, then α_{k}(n) = 3. So let n ≥ 7. Then, by induction on k and n,
α_{k}(n) = 1 + α_{k}(α_{k−1}(n)) ≤ 1 + α_{k}(n − 2) ≤ 1 + n − 4 < n − 2. QED
Claim 2: We have α_{k+1}(n) ≤ α_{k}(n) for all k and n. Moreover, for k ≥ 2 the inequality is strict if and only if α_{k}(n) ≥ 4.
Proof: The claim is easily established for α_{k}(n) ≤ 3, so suppose α_{k}(n) ≥ 4. By Claim 1,
α_{k+1}(n) = 1 + α_{k+1}(α_{k}(n)) ≤ 1 + α_{k}(n) − 2 < α_{k}(n). QED
Corollary 3: We have α_{k}(n) = o(n) for all k ≥ 2.
Proof: By Claim 2, since α_{2}(n) = Θ(log n) = o(n). QED
Claim 4:We have α_{k+1}(n) = o(α_{k}(n)) for all k ≥ 1.
Proof: By Corollary 3 we have
α_{k+1}(n) = 1 + α_{k+1}(α_{k}(n)) = 1 + o(α_{k}(n)). QED
In fact, Claim 4 can be strengthened. Given an integer r ≥ 1, let f^{(r)} denote the rthfold composition of the function f. Then,
Claim 5: α_{k+1}(n) = o(α_{k}^{(r)}(n)) for all fixed k and r.
Proof: Iterating r times the definition of α_{k+1}(n), and applying Corollary 3,
α_{k+1}(n) = r + α_{k+1}(α_{k}^{(r)}(n)) = r + o(α_{k}^{(r)}(n)). QED
Thus, we have log* n = o(log log log n), α_{4}(n) = o(log* log* log* log* n), etc.
By Claim 2, for every fixed n ≥ 5, the sequence
α_{1}(n), α_{2}(n), α_{3}(n), ...
decreases strictly until it settles at 3. For example, for n = 9876! we obtain the sequence
3.06×10^{35163}, 116812, 6, 4, 3, 3, 3, ...
The inverse Ackermann function α(n) assigns to each integer n the smallest k for which α_{k}(n) ≤ 3:
α(n) = min { k : α_{k}(n) ≤ 3 }.
Thus, α(9876!) = 5.
Claim 6: We have α(n) = o(α_{k}(n)) for every fixed k.
Proof: Let m = α_{k+1}(n). Then the (m − 2)nd term of the sequence
α_{k+1}(n), α_{k+2}(n), α_{k+3}(n), ...,
namely α_{k+m−2}(n), already equals 3. Thus,
α(n) ≤ k + m − 2 = k − 2 + α_{k+1}(n) = o(α_{k}(n)). QED
There is also a twoparameter version of the inverse Ackermann function that sometimes comes up (for example, in the running time of the UnionFind algorithm mentioned above). This twoparameter function can be defined as:
α(m, n) = min { k : α_{k}(n) ≤ 3 + m / n }.
This definition differs by at most a small additive constant from the "usual" definition of α(m, n) found in the literature. And as before, we defined it directly, without making mention of the rapidlygrowing Ackermann function.
The function α(m, n) satisfies the following properties:
 α(m, n) ≤ α(n) for every m and n.
 α(m, n) is nonincreasing in m.
 If m = nα_{k}(n) then α(m, n) ≤ k.