Prove or disprove $f \in O(g)$, with $f=5^{\log(n)^2}$ and $g = n^{\log(n)}$

Question

I have a feeling $f$ grows faster than $g$, and therefore it is not the case that $f \in O(g)$, but no matter how much I try, I do not see how to prove it.

Any help?

Answer 1

I am assuming all logarithms are in base $2$, but the conclusion wouldn't change if the $\log$ was the natural one.

So, you have $$ f(n) = 5^{\log(n)^2} = 2^{\log(5)\cdot\log(n)^2} $$ while $$ g(n) = n^{\log(n)} = 2^{\log(n)\cdot\log(n)} = 2^{\log(n)^2} $$

Therefore, $$ \frac{f(n)}{g(n)} = 2^{\log(5)\cdot\log(n)^2 - \log(n)^2} = 2^{(\log 5 - 1)\log(n)^2} \xrightarrow[n\to\infty]{} \infty $$ since $\log 5 -1 > 0$. Can you conclude?

Answer 2

The base that you take the logs do matter. For example on the one hand let's assume that the base is much bigger than 5; e.g, for example $\log n \doteq \log_{125} n$:

$$5^{\log^2_{125} n} = (5^{\log_{125} n})^{\log_{125} n} = (n^{\frac{1}{3}})^{\log_{125} n} = (n^{\log_{125} n})^{\frac{1}{3}} = g^{\frac{1}{3}}.$$

On the other hand let us now assume that the base is $2<5$ e.g, for example $\log n \doteq \log_{2} n$:

$$5^{\log^2_2 n} > 4^{\log^2_2 n} = (4^{\log_2 n})^{\log_2 n} = (n^2)^{\log_2 n} = (n^{\log_2 n})^2 = g^2.$$

So can you conclude for yourself the following: Iff the base is 5 or greater (e.g., 10) then $f \in O(g)$. If the base is less than 5 (i.e., 2 or $e$) then $f \not \in O(g)$.