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