Showing that $\log(n)^{\log(\log(n))} \in \mathcal{O}(n)$

Question

I want to show that

$$\log(n)^{\log(\log(n))} \in \mathcal{O}(n)$$

where $n \in \mathbb{N}_{≥2}$, and $\mathcal{O}$ is the big-O-notation.

It seems like a relatively simply statement, but so far, I've had no luck. I first started with the limit $\lim_{n \to \infty} \frac{\log(n)^{\log(\log(n))}}{n}$. In order to show the statement, it would be sufficient to show that this limit is $< \infty$. I searched for any way to simplify the expression, but so far couldn't find any. Sure we can write the limit as $\lim_{n \to \infty} \frac{\log(n)}{n^{\frac{1}{\log(\log(n))}}}$, but that doesn't seem to help either.

Next I thought about considering the derivative of $\log(n)^{\log(\log(n))}$. If it's derivative is bounded, then it grows at most linearly, which would also show the statement. Unfortunately though, it's derivative is (according to Wolframalpha) $\frac{2 \log^{\log(\log(n))-1} (n)\log(\log(n))}{n}$ which looks even more complicated than the limit I wanted to examine before, and it is (to me at least) not visible right away why this derivative must be bounded.

I also thought about induction arguments. When looking at a graph of the function, I noticed that $\log(n)^{\log(\log(n))}$ gets more and more flat for higher $n$, so maybe I can use an induction argument by fixing a fitting $c \in \mathbb{R}_{> 0}$ and showing that $\log(n)^{\log(\log(n))} ≤ c n$ for almost all $n \in \mathbb{N}$?

The way this exercise was posed to me makes me think that I'm probably thinking way too complicated and that there is a much easier way to show the desired statement, but so far, I haven't found any way that works.

Answer 1

Set $e^t = \log n$. Then LHS grows as $e^{t^2}$ and RHS as $e^{e^{t}}$

Answer 2

Assuming the logarithms are in base $2$ (this does not change anything, the argument would go as well if in another base, up to changing the $2$ to another number): You can write $$(\log n)^{\log \log n} = 2^{\log\log n\cdot \log \log n} = 2^{(\log \log n)^2}$$ and $n = 2^{\log n}$. Thus, $$ 0 \leq \frac{(\log n)^{\log \log n}}{n} = 2^{(\log \log n)^2-\log n} \xrightarrow[n\to\infty]{}0 $$ as $(\log \log n)^2 = o(\log n)$ (so that the exponent goes to $-\infty$). This implies $\frac{(\log n)^{\log \log n}}{n}$ is bounded, and therefore that $(\log n)^{\log \log n} = O(n)$.

Answer 3

We want to compare $e^{(\log\log n)^2}$ and $e^{\log n}$. Knowing that $$ \sup _{x\geq 1} \frac{\log(x)}{x} = e^{-1}, $$ we have $$ \frac{(\log\log n)^2}{\log n} = \left(\frac{2\log(\sqrt{\log n})}{\sqrt{\log n}} \right)^2\leq 4e^{-2} =:c < 1 $$ and thus $$ (\log n)^{\log\log n}=e^{(\log\log n)^2}\leq e^{c\log n}=n^c, $$ which slightly better then $(\log n)^{\log\log n}\in \mathcal O(n)$.