= Solution
For <natural logarithms> and sufficiently large $n$, take the <logarithm> of the positive expression:
$$
\log\left((\log n)^{\log\log n}\right)=(\log\log n)^2.
$$
Set $t=\log\log n$. Then $\log n=e^t$. The <exponential function> grows faster than $t^2$: for example, its power series gives $e^t\geq t^3/6$ for $t>0$, so $t^2/e^t\leq6/t\to0$. In particular, eventually $(\log\log n)^2\leq\log n$. Exponentiating yields
$$
\boxed{(\log n)^{\log\log n}\leq n\text{ eventually},\qquad (\log n)^{\log\log n}=O(n)}.
$$
For logarithms to a fixed base $b>1$, the natural logarithm of the left side is $(\log\log n-\log\log b)^2/\log b$, still smaller than $\log n$ eventually. The <big O notation> conclusion is therefore independent of that base choice.
Back to article page
