Does $O(n\cdot n!) = O(n!)$?

92 Views Asked by At

Does $O(n\cdot n!) = O(n!)$?

I know that $n*n! < (n+1)!$, and in Big Oh we usually throw out constants, so it seems like we could make this conclusion. However I am not sure how to show this mathematically.

2

There are 2 best solutions below

0
On BEST ANSWER

Look at the ratio:

$$\lim_{n\to\infty}\frac{n\cdot n!}{n!}=\lim_{n\to\infty}n=\infty\;,$$

so $n\cdot n!$ cannot be $O(n!)$.

1
On

We don't throw out constants. See, suppose we have $O(n^2)$; now what is that little figure 2? A variable? Definitely not. A constant? Surely! Can't we just throw it away?

We may throw out additive constants, but that's another story.