# If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?

Just as I asked in the title: if my algorithm has complexity $$O(n!\times n)$$, can I just write $$O(n!)$$, or I have to keep it like $$O(n!\times n)$$?

The function $$n! \cdot n$$ grows faster than $$n!$$, so it is not the case that $$n! \cdot n$$ is $$O(n!)$$. Therefore if all you know about an algorithm is that it runs in time $$O(n! \cdot n)$$, you cannot conclude that it runs in time $$O(n!)$$.

What you can do is "O tilde" notation, and write $$\tilde{O}(n!)$$. The meaning of "O tilde" is not completely standard, so you will have to explain that for you, $$\tilde{O}$$ suppresses factors which are polynomial in $$n$$.

• Thank you for the info! The "O tilde" seems useful. – ellamenopee Apr 3 '19 at 20:02

No. You can't. As $$\lim_{n\to\infty} \frac{n!}{n! \times n} = 0$$. Hence, $$n! \times n = \omega(n!)$$ or $$n! = o(n\times n!)$$ (little-oh).

If you care about the actual sizes, you need to keep the $$n$$. You could switch to $$O((n+1)!)$$ if that is easier for you.

But maybe you only actually care about how fast the logarithm grows, and $$\log(n!) = O(\log (n \cdot n!))$$.

• I guess you mean that $\log (n\,n!)=O(\log n!)$. What you've written is true but kinda the wrong way around. – David Richerby Apr 4 '19 at 20:50
• You’re right, but once you take the logarithm many things become right because they turn into constants or small differences. – gnasher729 Apr 4 '19 at 23:11
• It seems the log made removing $n$ possible, but only possible when there is log – ellamenopee Apr 5 '19 at 18:30