The iterated logarithm is defined as follows:
$\log^*(n):=\begin{cases}0, & \text{ if } n \leq 1 \\ 1 + \log^*(\log n), & \text{ otherwise}.\end{cases}$
Now, I am wondering what the relation between $\log^*(n)$ and the following quantity $f(n)$ is:
$f(n):=\begin{cases}0, & \text{ if } n \leq 1 \\ 1 + f(\log^3 n), & \text{ otherwise}.\end{cases}$
So $\log^*(n)$ indicates the number of times we have to apply the logarithm in order to reach $1$. And $f(n)$ indicates the number of times we have to apply $\log^3(\cdot)$ to reach $1$.
Can you tell me whether $f(n)=\Theta(\log^*(n))$ or even express $f(n)$ in terms of $\log^*(n)$?
Thanks a lot.
Notice that
$f(n)=1+f(\log^3(n))=2+f(\log^3(\log^3(n)))=2+f(27\log^3(\log(n)))\\=3+f(27\log^3(27\log(\log(n))))=\dots$
And thus, the inverse of $f$ is asymptotically $f^{-1}(n)=\Theta(e^{\frac1{27}e^{\frac1{27}e^{\dots}}})$ which leads us to
$$(e^{1/3})\uparrow\uparrow n<k\cdot f^{-1}(n)<(\frac1{27}e)\uparrow\uparrow n$$
Likewise, the inverse of the iterated logarithm has bounds:
$$e\uparrow\uparrow n<\operatorname{logs}^{-1}(n)<e\uparrow\uparrow(n+1)$$
Thus, it is clear that
$$\operatorname{logs}^{-1}(n)>>f^{-1}(n)$$
Thus,
$$f(n)>>\operatorname{logs}(n)$$
And so we cannot compare using even $\Theta(\cdot)$.