Is $(n!)^n$ complexity just said to be $O(n!)$ complexity?

Question

I know that $n!$ complexity is higher than exponential complexity and big-O notation says always use the highest growing $n$ term for the naming. But, seeing as this is a factorial to the power of $n$ rather than $n!+x^n$, does that make a difference or would it still simply just be refered to as facorial complexity?

Answer 1

First mathematically you don't have to only use the highest growing term, it's just one thing we do to shorten it.

If you're really have $O(n!^n)$ then it's definitely larger than both $O(n^n)$ and $O(n!)$, but if you compare $O(n^n)$ and $O(n!)$ they are about the same.

Let's examine the latest closer. $n! = \prod_{j\le n} j \le \prod_{j\le n}n = n^n$, so obviously $n!$ is $O(n^n)$

On the other hand by stirling approxmation we have $n! \approx \sqrt{2\pi n}(n/e)^n$ so $n^n \approx n! e^{n}/\sqrt{2\pi n}$ so it will not be bounded by $n!$. More strictly it's enough to observe that if we consider $n^n/n! = \prod^n_1{n/j} = n\prod^n_2{n/j}$, but since $n\ge j$ in the factors we get $n^n/n! \ge n$, that is $n^n \ge n! n$ (which means there's no constant $K$ such that $n^n \le n!K$ for all $n$).