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

Question

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?

• nir shahar: 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))$.
• Reijo Jaakkola: @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)$.
• DMGregory: @nirshahar I think that would make for a good answer.
• nir shahar: Thanks, I will post ot as an answer instead of a comment ;)

Answer 1

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