# Inverse of Ackermann function and $\log^* n$

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

• This is not what is written here. Commented Nov 20, 2021 at 16:02

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)$$.
• 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. Commented Nov 20, 2021 at 20:46 • My question is how we can show$\alpha(n)=o(\log^*n)$? Commented Nov 21, 2021 at 1:06 • @Ahmad, I will update to show that. Basically,$\alpha(A(5,m))=o(m)$while$\log^*(A(5,m))=\omega(m)\$. Commented Nov 21, 2021 at 1:41