Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?

Question

Which function grows faster:

$$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$

Which is true?

• $f(n) = O(g(n))$
• $g(n) = O(f(n))$
• i.e., $f(n) = \Theta(g(n))$
• none of the above?

For lower values of $n$, it looks like $f(n)$ is bigger, but I'm not sure for very big values of $n$.

Answer 1

With some manipulations: $$ f(n) = 4^{n^2 \log n} = (2^2)^{n^2 \log n} = (2^{\log n})^{2n^2} = n^{2 n^2}. $$ and: $$ g(n)= (n!)^n \le (n^n)^n = n^{n^2}. $$

Taking the limit: $$ \lim_{n \to \infty} \frac{f(n)}{g(n)} \ge \lim_{n \to \infty} \frac{n^{2 n^2}}{n^{n^2}} = \lim_{n \to \infty} n^{n^2} = +\infty. $$