3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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