# Arguing that the inverse of Ackermann function is upper bounded by a logarithmic function (i.e. $\alpha(n) = O(\lg n)$)

The text Introduction to Algorithms by Cormen, et. al. defines the Ackermann Function $$A$$ as follows: For integers $$k \geq 0$$ and $$j \geq 1$$, we define the function $$A_k(j)$$

$$A_{k}(j) = \begin{cases} j+1 &\quad\text{if } k=0\\ A_{k-1}^{(j+1)}(j)&\quad\text{if } k \geq 1\\ \end{cases}$$

The inverse of the function $$A_k(n)$$, for integer $$n \geq 0$$,is defined by

$$\alpha(n) = \min \{k : A_k(1) \geq n\}$$ .

$$\alpha(n)=\begin{cases} 0 \quad\text{ for } 0\leq n\leq 2 \\ 1 \quad\text{ for } n=3\\ 2 \quad\text{ for } 4\leq n\leq 7\\ 3 \quad\text{ for } 8\leq n\leq 2047\\ 4 \quad\text{ for } 2048\leq n\leq A_4(1)\\ \end{cases}$$ It is only for impractically large values of $$n$$ (greater than $$A_4(1)$$, a huge number) that $$\alpha(n) > 4$$, and so $$\alpha(n) \leq 4$$ for all practical purposes.

From the above analysis we can say that for $$n$$ (with in practical limits), we have $$\alpha(n) \leq 4 \leq \lg n \text{ for all } n \geq 16$$

Hence we can say that $$\alpha (n)= O(\lg n)$$, when $$n$$ is within practical limits.

This is the analysis that I thought of, but what bugs me is that asymptotic analysis should be for $$n$$ when it is arbitrarily high, i.e. when $$n \rightarrow \infty$$. In this case though $$A_4(1)$$ is a very very large number but it is after all finite and in the analysis we assumed $$n$$ to be at most $$A_4(1)$$. In that case, isn't my analysis flawed or abuse of asymptotic Big-Oh notation? If so (which I guess definitely is) how to process correctly?

• yes, it is an abuse of big-O notation. To actually prove the theorem for all $n$ (not only those within practical limits), try to show instead that the ackerman function is $\Omega(2^n)$. This will help you to prove that $\alpha(n) = O(\log(n))$. Oct 26 '21 at 19:42
• @nirshahar Well, Ackermann function is well-known to grow faster than any primitive recursive, so it is $\Omega(f(n))$, for any primitive recursive function $f(n)$. Oct 26 '21 at 20:09
• @nirshahar I think that would make for a good answer. Oct 27 '21 at 1:51
• Thanks, I will post ot as an answer instead of a comment ;) Oct 27 '21 at 5:00

Yes, it is an abuse of big-O notation.

Hint: To actually prove the theorem for all $$n$$ (not only those within practical limits), try to show instead that the ackerman function is $$\Omega(2^n)$$. This will help you to prove that $$\alpha(n) = O(\log(n))$$.