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

Question

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.

score 10 · Accepted Answer · answered Sep 14 '15 at 06:07

10

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

answered Sep 14 '15 at 06:07

Brian M. Scott

616,228

score 2 · Answer 2 · answered Sep 14 '15 at 08:47

2

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.

answered Sep 14 '15 at 08:47

Ivan Neretin

12,835

Right, I was referring to additive constants. However I was unsure whether you could still do this if a function was operating on the sum of a variable and a constant. The above answers have cleared this up, though. – flubsy Sep 14 '15 at 23:16

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

2 Answers2