4
$\begingroup$

Which one is asymptotically larger? $\log^*(\log(n))$ or $\log(\log^*(n))$? I think they are asymptotically tight bounds for each other (one is $\Theta$ of the other).

$\endgroup$
4
$\begingroup$

Suppose that $\log^* n = k$. This means it takes $k$ many $\log$'s to reduce $n$ below some constant. Therefore $\log^* \log n = k-1$ (assuming $k$ is not too small), whereas $\log \log^* n = \log k$.

$\endgroup$
2
$\begingroup$

Suppose $f_1(n)=\log \log^{*}(n)$, and $f_{2}(n)=\log^{*} \log(n)$.

Let $n=2^m$ then According the definition of iterated function:

$\log^* n$ (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

So $$f_1(2^m)=\log \log^*(2^m)=\log \log^*\log(2^m)+1=\log\log^*m+1=\theta(\log\log^*m)$$

and $$f_2(2^m)=\log^*\log(2^m)=\log^*(m)+1=\theta(\log^*m)$$ Finally, for sufficient large $n$ (i.e. as $n\to \infty$) we conclude that: $$f_1(2^m)=O(f_2(2^m)).$$ Because let $\log^*(m)=k$ then: $$f_1(2^m)=\log k$$ and $$f_2(2^m)=k.$$ Obviously order of growth two mentioned function follow below relation $$f_1(2^m)=O(f_2(2^m)).$$

$\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.