4
$\begingroup$

Consider inverse of Ackermann function, can we conclude that the growth rate of it as the same as growth rate $\log^*n$?

$\endgroup$
1
  • 2
    $\begingroup$ This is not what is written here. $\endgroup$
    – Nathaniel
    Nov 20 at 16:02
3
$\begingroup$

No, since the Ackermann function grows faster than any primitive recursive function.

The iterated logarithm is one of the two inverse functions of tetration. As a primitive recursive function, Tetration with base 2 is "roughly" equivalent to $A(4,n)$, where $A(m,n)$ is the Ackermann function of two variables . $A(n,n)$ is assumed to be the Ackermann function in the question.

Exercise. Show that the inverse of Ackermann function grows slower than $\log^*(\log^∗n)$.

$\endgroup$
5
  • $\begingroup$ Here is one more exercise. Define the iterated "iterated logarithm". Show that the inverse of Ackermann function grows slower than it. $\endgroup$
    – John L.
    Nov 20 at 20:33
  • $\begingroup$ This answer is meant to provide an intuitive understanding, assuming the basic knowledge of primitive recursive function or the basic properties of the Ackermann functions. The terminologies and argument here is not meant to be strict. For example, $f$ grows faster than $g$ does not imply "the inverse" of $f$ grows slower than "the inverse" of $g" necessarily. $\endgroup$
    – John L.
    Nov 20 at 20:46
  • $\begingroup$ My question is how we can show $\alpha(n)=o(\log^*n)$? $\endgroup$
    – Ahmad
    Nov 21 at 1:06
  • 1
    $\begingroup$ @Ahmad, I will update to show that. Basically, $\alpha(A(5,m))=o(m)$ while $\log^*(A(5,m))=\omega(m)$. $\endgroup$
    – John L.
    Nov 21 at 1:41
  • $\begingroup$ Thank you so much. $\endgroup$
    – Ahmad
    Nov 21 at 1:46

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.