0
$\begingroup$

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)$?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you for the info! The "O tilde" seems useful. $\endgroup$ – ellamenopee Apr 3 at 20:02
2
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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!))$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.