2
$\begingroup$

Assume a function $T(n)$: $$T(n)=\log{\log^{*}{n}}$$ Let's define: $$\log^{*}{n}=\min\{i\ge{0}:\log^{(i)}{n}\le1\}$$ and: $$\log^{(i)}{n}=\log{(\log^{(i-1)}{n})}$$ Is the following $f(n)$ function an upper bound or a lower bound of $T(n)$? $$f(n)=\log^{*}{\log{n}}$$


To see if $f(n)$ could possibly be an upper bound, I feel like the following limit needs to be gone through: $$\lim_{n\to\infty}{T(n)}=\lim_{n\to\infty}{\log{\log^{*}{n}}}=?$$ Now I wonder if the above limit might boil down to this: $$\lim_{n\to\infty}{T(n)}=\lim_{n\to\infty}{\log{(\min{\{\log\log\log\cdots\log^{(0)}{n}\}})}}$$ I'm not quite sure how to solve the above limit to get an idea of the upper bound of $T(n)$. Also, the lower bound is another story which I have little idea about.

$\endgroup$
2
$\begingroup$

For $n$ satisfying $\log n > 1$, we have $\log^* \log n = \log^* n - 1$ (exercise). On the other hand, $\log \log^* n $ is much smaller than $\log^* n$. Hence $\log \log^* n = o(\log^* \log n)$.

$\endgroup$

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.