2

I'm not entirely sure if this proof would suffice, but here's what I have,

$$\text{Show }n! \in O(n^n) \text{ but } n^n \notin O(n!).$$

Consider, $ c \geq\frac{|f(n)|}{g(n)}$ by Big O definition. Let $f(n) = n!$ and $g(n) = n^n \hspace{0.2cm}\forall n \geq 1$. Then $ c \geq \displaystyle{\lim_{n \to \infty}} \dfrac{|n!|}{n^n} = 0$. Next consider $f(n) = n^n$ and $g(n) = n!$. Then $ c \geq \displaystyle{\lim_{n \to \infty}} \dfrac{|n^n|}{n!} = \infty$. Hence, $n! \in O(n^n)$ but $n^n \notin O(n!)$ as required.

Is this acceptable?

Philip
  • 198
  • 1
    You're asserting the two limits, but not proving that they are correct. Also, what is $c$ in either case? In the second one, there is no such $c\in \mathbb{R}$ with $c\ge \infty$. – Mark Viola Apr 29 '17 at 02:42
  • To make @Dr.MV's comment more precise, you have simply restated the question. – Igor Rivin Apr 29 '17 at 03:08
  • So I just need to show the limits are $0$ and $\infty$ respectively? – Philip Apr 29 '17 at 03:25
  • @Philip All you need to show, which is trivial, is $n!\le n^n$ and that $n^n\ge n,n!$. Then, $\frac{n!}{n^n}\le 1=C$ and $n!=O(n^n)$. And $\frac{n^n}{n!}\ge n$. – Mark Viola Apr 29 '17 at 03:31

1 Answers1

1

Note that it is straightforward to show that $n^n\ge n\,n!$ (e.g., one can use induction).

Then we have

$$\frac{n!}{n^n}\le 1=C$$

and $n!=O(n^n)$.

On the other hand, we have

$$\frac{n^n}{n!}\ge n$$

Hence, for any fixed number $C>0$, however, large, there is a number $n>C$ such that $\frac{n^n}{n!}\ge n>C$, Therefore, there is no number $C>0$ such that for sufficiently large $n$, $\frac{n^n}{n!}\le C$ and $n^n\ne O(n!)$.

And we are done!

Mark Viola
  • 179,405