patternMinor
Inverse of Ackermann function and $\log^* n$
Viewed 0 times
inverselogfunctionandackermann
Problem
Consider inverse of Ackermann function, can we conclude that the growth rate of it as the same as growth rate $\log^*n$?
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#145951, answer score: 4
Revisions (0)
No revisions yet.