The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann. $$\alpha_1(n) = [n/2]$$ $$\alpha_2(n) = [\log_2 n]$$ $$\alpha_3(n) = \log^* n$$ $$...$$ $$\alpha_k(n) = 1 + \alpha_k(\alpha_{k−1}(n))$$ and $$\alpha(n) = \min\{k: \alpha_k(n)\leq 3\}$$ [Notation: [x] means that we round up x to the nearest integer, while log∗ is the iterated log function discussed here: http://en.wikipedia.org/wiki/Iterated_logarithm ]

My question is: What is the function $$k(n) = \min \{k: \alpha_k(n) \leq k\}$$ Clearly $1\ll k(n) \leq \alpha(n)$. What tighter bounds can one give on $k(n)$? Is $k(n) \leq \log\alpha(n)$?

  • $\begingroup$ I know why $k(n) \leq \alpha(n)$, but could you explain why is $k(n) \ll \alpha(n)$? $\endgroup$
    – jbapple
    Mar 21, 2015 at 21:31
  • $\begingroup$ Ok, edited to the uncontroversial $k(n)<\alpha(n)$. $\endgroup$ Mar 21, 2015 at 21:37
  • 3
    $\begingroup$ @DanaMoshkovitz: I approximated the definitions using the Ackermann hierarchy I'm familiar with: $\alpha(n)=\min\{k: A_k(1)\geq n\}$ and $k(n)=\min\{k:A_k(k)\geq n\}$. With a typical definition of the Ackermann functions, $A_{k+1}(1)=A_k(A_k(1))\geq A_k(k)$. Hence if $A_k(k)\geq n$ then $A_{k+1}(1)\geq n$, i.e., $k(n)\geq\alpha(n)-1$. (I hope I haven't made a mistake in there.) $\endgroup$
    – Sylvain
    Mar 21, 2015 at 23:13
  • 1
    $\begingroup$ @DanaMoshkovitz: to clarify, I'm using $A_1(n)=2n$ and $A_{k+1}(n)=A_k^{n+1}(1)$, which grows slightly faster than your definition, e.g., $A_2(n)=2^{n+1}$ instead of $2^n$. It shouldn't have much of a consequence though: $\alpha(n)$ and $k(n)$ are pretty much the same thing. $\endgroup$
    – Sylvain
    Mar 21, 2015 at 23:29
  • 1
    $\begingroup$ @DanaMoshkovitz: I don't see why $k(n)<\alpha(n)$. For infinitely many values of $n$ you will have $\alpha(n)=k(n)$, i.e. whenever $A_k(k)<n\leq A_{k+1}(1)<A_{k+1}(k+1)$; because $A_{k+1}(1)-A_k(k)$ grows fast, you have longer and longer such sequences. With your definitions it's even possible to have $\alpha(n)<k(n)$: $\alpha_2(8)=3>2$ hence $\alpha(8)=2$ but $k(8)=3$. $\endgroup$
    – Sylvain
    Mar 22, 2015 at 8:44

2 Answers 2


Let $A_k$ be the inverse of $\alpha_k$. $A_1(x) = 2x, A_2(x) = 2^x, \dots$. I claim that $k^{-1}(x) = A_x(x)$.

Since $x = \alpha_x(A_x(x))$, and since $\forall z, \alpha_y(z) > \alpha_x(z)$, $\alpha_y(A_x(x)) > \alpha_x(A_x(x)) = x$. As a result $k(A_x(x)) = x$.

Now consider the value of $\alpha(k^{-1}(n)) = \alpha(A_n(n))$. By definition of $\alpha$, this is $\min_z \{\alpha_z(A_n(n)) \leq 3\}$. We know that $\alpha_n(A_n(n)) = n$, so $\alpha(A_n(n)) > n$. I claim that $\alpha(A_n(n)) \leq n+2$. $\alpha_{n+1}(A_n(n)) = 1+\alpha_{n+1}(n)$. Now $\alpha(n) = \min_z\{\alpha_z(n) \leq 3\}$, so $\alpha_{\alpha(n)}(n) \leq 3$. Since $n+1 > \alpha(n)$, $\alpha_{n+1}(n) \leq 3$, so $\alpha_{n+1}(A_n(n)) \leq 4$. Thus, $\alpha_{n+2}(A_n(n)) = 1 + \alpha_{n+2}(\alpha_{n+1}(n)) \leq 1 + \alpha_{n+2}(4) \leq 3$.

So, we have $n < \alpha(k^{-1}(n)) \leq n+2$, so $k$ and $\alpha$ are essentially equal.

  • 9
    $\begingroup$ And let me add that all these functions are just different complicated ways of writing the number 4. $\endgroup$ Mar 23, 2015 at 4:32

This is incorrect; see the comments.

A function very close to this one was called "$\alpha^*$" and used in Pettie's "Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture", in which he showed that "$n$ deque operations [in a splay tree] take only $O(n\alpha^*(n))$ time, where $\alpha^*(n)$ is the minimum number of applications of the inverse-Ackermann function mapping $n$ to a constant."

This function is very slow growing, and is slower growing than $\log \alpha(n)$. Consider the function $f:\mathbb{N} \to \mathbb{N}$

$$ f(n) = \cases{1 & n = 0\\2^{f(n-1)} & n > 0} $$

This function is roughly as fast growing as $A(4,n)$, so is more slowly growing than $A'(n) = A(n,n)$. Now I'll evaluate $\log \alpha(n)$ and $\alpha^*(n)$ on $A'(f(n))$:

$$ \log \alpha(A'(f(n))) = \log f(n) = f(n-1)$$

$$\alpha^*(A'(f(n))) = 1 + \alpha^*(f(n)) < 1 + \alpha^*(A'(n)) < 2 + \alpha^*(n)$$

Since $f(n-1) \in \omega(2+\alpha^*(n))$, $\log \alpha(n)$ is much faster growing than $\alpha^*(n)$.

  • $\begingroup$ What is the relation between alpha^* and k(n)? (note that in the definition of k(n) I use the notation alpha_k(n) defined in the link I had in the question) $\endgroup$ Mar 21, 2015 at 21:14
  • $\begingroup$ Oh, I'm sorry, I read your $\alpha_k$ as $\alpha^k$! $\endgroup$
    – jbapple
    Mar 21, 2015 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.