<p>This is incorrect; see the comments.</p>

<p><s>A function very close to this one was called "$\alpha^*$" and used in <a href="http://web.eecs.umich.edu/~pettie/papers/Deque.pdf" rel="nofollow">Pettie's "Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture"</a>, 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."</p>

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

<p>$$
f(n) = \cases{1 &amp; n = 0\\2^{f(n-1)} &amp; n &gt; 0}
$$</p>

<p>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))$:</p>

<p>$$ \log \alpha(A'(f(n))) = \log f(n) = f(n-1)$$</p>

<p>$$\alpha^*(A'(f(n))) = 1 + \alpha^*(f(n)) &lt; 1 + \alpha^*(A'(n)) &lt; 2 + \alpha^*(n)$$</p>

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

CC BY-SA 3.0
2015-03-21T21:14:16.657Z
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)
Dana Moshkovitz
CC BY-SA 3.0
2015-03-21T21:29:10.457Z
Oh, I'm sorry, I read your $\alpha_k$ as $\alpha^k$!
jbapple
CC BY-SA 3.0
2015-03-21T20:53:11.070Z
2015-03-21T21:37:45.100Z
2015-03-21T21:37:45.100Z
jbapple
<p>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)$.</p>

<p>Since $x = \alpha_x(A_x(x))$, and since $\forall z, \alpha_y(z) &gt; \alpha_x(z)$, $\alpha_y(A_x(x)) &gt; \alpha_x(A_x(x)) = x$. As a result $k(A_x(x)) = x$.</p>

<p>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)) &gt; 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 &gt; \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$.</p>

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

CC BY-SA 3.0
2015-03-23T04:32:07.660Z
And let me add that all these functions are just different complicated ways of writing the number 4.
Sariel Har-Peled
CC BY-SA 3.0
2015-03-21T23:49:53.253Z
2015-03-21T23:49:53.253Z
jbapple
<p>The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: <a href="http://www.gabrielnivasch.org/fun/inverse-ackermann" rel="nofollow">http://www.gabrielnivasch.org/fun/inverse-ackermann</a>. 
$$\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: <a href="http://en.wikipedia.org/wiki/Iterated_logarithm" rel="nofollow">http://en.wikipedia.org/wiki/Iterated_logarithm</a> ]</p>

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

CC BY-SA 3.0
2015-03-21T21:31:18.393Z
I know why $k(n) \leq \alpha(n)$, but could you explain why is $k(n) \ll \alpha(n)$?
jbapple
CC BY-SA 3.0
2015-03-21T21:37:29.843Z
Ok, edited to the uncontroversial $k(n)<\alpha(n)$.
Dana Moshkovitz
CC BY-SA 3.0
2015-03-21T22:55:02.647Z
I don't feel like checking with the particular definition of $\alpha(n)$ you are using, but for reasonable definitions and large enough $n$ you ought to have $\alpha(n)\leq k(n)+1$.
Sylvain
CC BY-SA 3.0
2015-03-21T23:00:14.637Z
I edited the question to clarify the definition I use. Why do you think that k(n) is alpha(n)-1?
Dana Moshkovitz
CC BY-SA 3.0
2015-03-21T23:13:52.623Z
@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.)
Sylvain
CC BY-SA 3.0
2015-03-21T23:29:52.167Z
@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.
Sylvain
CC BY-SA 3.0
2015-03-22T08:44:27.487Z
@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$.
Sylvain
<ds.algorithms><ds.data-structures><bounds>
Fun with inverse Ackermann
Dana Moshkovitz
# Fun with inverse Ackermann

(Asked by: username_0 on 2015-03-21)

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

**Tags:** ds.algorithms, ds.data-structures, bounds

> **Comments:**
> **username_1**: I know why $k(n) \leq \alpha(n)$, but could you explain why is $k(n) \ll \alpha(n)$?  
> **username_0**: Ok, edited to the uncontroversial $k(n)<\alpha(n)$.  
> **username_2**: I don't feel like checking with the particular definition of $\alpha(n)$ you are using, but for reasonable definitions and large enough $n$ you ought to have $\alpha(n)\leq k(n)+1$.  
> **username_0**: I edited the question to clarify the definition I use. Why do you think that k(n) is alpha(n)-1?  
> **username_2**: @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.)  
> **username_2**: @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.  
> **username_2**: @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$.  

---

## 2 answers

### Answer by username_1 on 2015-03-21. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_3**: And let me add that all these functions are just different complicated ways of writing the number 4.  

---

### Answer by username_1 on 2015-03-21. Score: 0

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"](http://web.eecs.umich.edu/~pettie/papers/Deque.pdf), 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)$.

> **Comments:**
> **username_0**: 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)  
> **username_1**: Oh, I'm sorry, I read your $\alpha_k$ as $\alpha^k$!  

---

