1
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ 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))$. $\endgroup$
    – nir shahar
    Oct 26 '21 at 19:42
  • $\begingroup$ @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)$. $\endgroup$ Oct 26 '21 at 20:09
  • $\begingroup$ @nirshahar I think that would make for a good answer. $\endgroup$
    – DMGregory
    Oct 27 '21 at 1:51
  • $\begingroup$ Thanks, I will post ot as an answer instead of a comment ;) $\endgroup$
    – nir shahar
    Oct 27 '21 at 5:00
1
$\begingroup$

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

$\endgroup$

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.