How do I prove that that $n \geq \log_2(n) ^{(\log_2(\log_2(n))}$ as n becomes large?

Question

More specifically, I am trying to show that the asymptotic complexity of a problem with that has the bounds $\Theta(\log{2}(n) ^{(\log_2(\log_2(n))})$ is less than that of a problem with the bounds $\Theta(n)$.

I tried to use L'Hospital's rule but the derivatives become too complicated for that to be a good solution. I suspect that there may be a substitution that I can make, but if there is I cannot see what it is.

Edit: I originally stated that the log term was greater, which is clearly an error.

Answer 1

I think you mean the inequality should be the other way around ? Take $ \log_2 $ of the inequality \begin{eqnarray*} \log_2 (n) \leq \left( \log_2( \log_2 (n)) \right)^2 \end{eqnarray*} Now let $n=2^{2^N}$ and we get \begin{eqnarray*} 2^N \leq N^2 \end{eqnarray*} which is obviously false for large $N$

Answer 2

The inequality goes the wrong way. $$(\log_2 n)^{\log_2 \log_2 n} = 2^{(\log_2 \log_2 n)^2}$$ while $$n = 2^{\log_2 n}$$ Now $\log_2 t = o(t^\alpha)$ for any $\alpha>0$ as $t \to \infty$. Taking $t = \log_2 n$ we have $\log_2 \log_2 n = o((\log_2 n)^{1/2})$ and $(\log_2 \log_2 n)^2 = o(\log_2 n)$.