Is $O(n^k n!)$ in same complexity class as $O(n!)$?

Question

Can $O(n^k n!)$ be simplified to $O(n!)$, let's say for $k=2$?

Answer 1

Unfortunately not. It may interest you to know the following fact: for any two functions $f, g: \mathbb{Z}^+ \to \mathbb{Z}^+$, we have that $$ O(f(n)) \text{ is the same as } O(g(n)) $$ if and only if there are constants $0 < c < C < \infty$ such that $$ c \le \frac{f(n)}{g(n)} \le C $$ for all $n$ (or, for all sufficiently large $n$ is good enough). In other words, $\frac{f(n)}{g(n)}$ should be bounded and bounded away from zero. If $\lim_{n \to \infty} \frac{f(n)}{g(n)} \in [0,\infty]$ exists, as will often be true in practice, this is equivalent to $$ 0 < \lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty. $$

In our case, $$ \frac{n^k n!}{n!} = n^k, $$ which approaches $\infty$, so $O(n^k n!)$ and $O(n!)$ are not equivalent.

However, the difference between $n^k n!$ and $n!$ in e.g. complexity theory, is minimal; since $n!$ is so large, the $n^k$ hardly matters much in comparison. Formally, we could say that they differ only by a polynomial factor. In many contexts (complexity theory in particular, since you used the computational complexity tag), we choose to ignore polynomial factors.

Answer 2

It cannot, as explained by another answer in this thread, but your intuition is correct that this is a useful way to think about the complexity. The notion you are looking for is not $O()$ but $O^*()$: it is true that $$O^*(n!) = O^*(n^k\cdot n!)$$

when $k$ is a constant. The idea is that one can say that $f(x)$ is in $O^*(g(x))$ whenever there is some polynomial function $p(x)$ such that $f(x)$ is in $O(p(x)\cdot g(x))$. (I think this is not quite right, so please don't depend on it.)

I would like to refer you to a Wikipedia article that discusses this but I can't find one. (Perhaps someone else can fix this?) However, What is the difference between the Big O and Big O star (asterisk) operator? discusses it a bit.