(Updated June 2009) 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 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 two-parameter 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, 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 hierarchyThe 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):
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 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 functionBy 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 The two-parameter version of the inverse Ackermann functionThere is also a two-parameter version of the inverse Ackermann function that sometimes comes up (for example, in the running time of the Union-Find algorithm mentioned above). This two-parameter 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 rapidly-growing Ackermann function. The function α(m, n) satisfies the following properties:
See also
R. Seidel, Understanding the inverse Ackermann function (PDF presentation). |
Fun >