11
$\begingroup$

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)$?

$\endgroup$
7
  • $\begingroup$ I know why $k(n) \leq \alpha(n)$, but could you explain why is $k(n) \ll \alpha(n)$? $\endgroup$ – jbapple Mar 21 '15 at 21:31
  • $\begingroup$ Ok, edited to the uncontroversial $k(n)<\alpha(n)$. $\endgroup$ – Dana Moshkovitz Mar 21 '15 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 '15 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 '15 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 '15 at 8:44
12
$\begingroup$

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.

$\endgroup$
1
  • 9
    $\begingroup$ And let me add that all these functions are just different complicated ways of writing the number 4. $\endgroup$ – Sariel Har-Peled Mar 23 '15 at 4:32
0
$\begingroup$

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)$.

$\endgroup$
2
  • $\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$ – Dana Moshkovitz Mar 21 '15 at 21:14
  • $\begingroup$ Oh, I'm sorry, I read your $\alpha_k$ as $\alpha^k$! $\endgroup$ – jbapple Mar 21 '15 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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