Find whether $f(n) = o(g(n))$ or $g(n) = o(f(n))$

Question

Find whether $f(x) = O(g(n))$ or $g(n) = O(f(x))$ where $$ f(n) = (\log n)^{\log n} \quad\quad\text{and}\quad\quad g(n) = 2^{(\log_2n)^2} $$

I found that $f(n) = n^{ \log {\log n}}$, but can't simplify $g(n)$.

Answer 1

$f(n) = \Bbb e ^{(\log \log n) \log n} = \big( \Bbb e ^{ \log n} \big) ^{\log \log n} = n ^{\log \log n}$.

$g(n) = 2^ {(\log _2 n) (\log _2 n)} = \big( 2^ {\log _2 n} \big) ^{\log _2 n} = n ^{\log _2 n} = n ^{\frac {\log n} {\log 2}}$.

Therefore, $\lim \limits _{n \to \infty} \frac {f(n)} {g(n)} = \lim \limits _{n \to \infty} n ^{\log \log n - \frac {\log n} {\log 2}} = \infty ^{- \infty} = 0$, therefore $f(n) = o (g(n))$ (mind you, it is "little o", not "big O"!).

Answer 2

$g(n) = \left(2^{\log_2 n}\right)^{\log_2 n} = O(n^{\log n})$

$f(n) = e^{(\log \log n) \log n} = O(n^{\log \log n})$

So $g$ asymptotically grows faster than $f$, so $f(n) = O(g(n))$ and not the other way around