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

105 Views Asked by At

I was reading about Bogo Sort average time complexity, which is $O(n \cdot n!)$. In this case, would it be right to just ignore the first factor n, following the rule

$$O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n!) < O(n^n)?$$

Is $O(n!)$ the same as $O(n \cdot n!)$? Or is $O(n \cdot n!) > O(n!)$?

1

There are 1 best solutions below

1
On BEST ANSWER

Here $n!=O(n\cdot n!)$ is true but $n\cdot n!=O(n!)$ is false, so they do not have the same time complexity. To show this clearly, you may use the limit definition, $n!=O(n\cdot n!)$ is equivalent to the statement

$$\limsup_{n \to \infty} \left|\frac{n!}{n\cdot n!}\right| =\lim_{n \to \infty} \frac{1}{n} < \infty,$$ which is true. Can you disprove $n\cdot n!=O(n!)$ by yourself?