The inverse Ackermann function (original) (raw)

Inverse Ackermann without pain

Updated February 27, 2007

The inverse Ackermann function is an extremely slow-growing function which occasionally turns up in computer science and mathematics. The function is denoted α(n) (alpha of n).

This function is most well-known in connection with the Union-Find problem: The optimal algorithm for the Union-Find problem runs in worst-case time Θ(_m_α(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.)

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, Springer-Verlag, 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 quickly-growing 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

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 floor function. 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):

We have α2(n) = [log2 _n_], and α3(n) is the iterated logarithm function, denoted log* n.

Claim 1: If n ≥ 3 then α_k_(n) ≤ n − 2.

Proof: By induction on k. The case k = 1 is clear. So assume k ≥ 2.

If n = 3, then α_k_(n) = 1; and if n = 4 or 5, then α_k_(n) = 2. So let n ≥ 6. 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, the inequality is strict if and only if α_k_(n) ≥ 3.

Proof: It is easily shown that if α_k_(n) = 0, 1, or 2, then α_k_+1(n) = α_k_(n). So suppose α_k_(n) ≥ 3. 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 _r_-th-fold 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.

The inverse Ackermann function

By Claim 2, for every fixed n ≥ 4, the sequence

α1(n), α2(n), α3(n), ...

decreases strictly until it settles at 2. For example, for n = 9876! we obtain the sequence

3.06×1035163, 116811, 5, 3, 2, 2, 2, ...

The inverse Ackermann function α(n) assigns to each integer n the smallest k for which α_k_(n) ≤ 2:

α(n) = min { k : α_k_(n) ≤ 2 }.

Thus, α(9876!) = 5.

Claim 6: We have α(n) = o(α_k_(n)) for every fixed k.

Proof: Let m = α_k_+1(n). Then the (m − 1)-st term of the sequence

α_k_+1(n), α_k_+2(n), α_k_+3(n), ...,

namely α_k_+_m_−1(n), already equals 2. Thus,

α(n) ≤ k + m − 1 = k − 1 + α_k_+1(n) = o(α_k_(n)). QED

See also

• R. Seidel, Understanding the inverse Ackermann function (PDF presentation).