MHB Is n! in O(4^n) or 4^n in O(n!)?

[shamieh]

Which of the following identities are true. Justify your answer.
a)$n! = O(4^n)$
b)$4^n = O(n!)$

I have NO clue what to do here. First I was thinking let $n = 0$ so that $1 = O(1)$ (constant time complexity?)

 

[evinda]

It holds that:$$n!=1 \cdot 2 \cdots (n-1) \cdot n \geq 1 \cdot 2 \cdot 3 \cdot 4 \cdot 4 \cdots 4=1 \cdot 2 \cdot 3 \cdot 4^{n-3} \geq \frac{3}{32} \cdot 4^n$$

What can we deduce from that?

 

[shamieh]

Here is what I've came up with..

I know that: $f(x) = O(g(x))$ iff $\exists$ positive constants $C$ and $n_0$ $|0 \le f(n) \le c * g(n),$ $\forall$ $n \ge n_0|$

So I found that $n! \notin O(4^n)$ by letting $n = 10$ and letting $c = 1$. Then I found that $4^n \in O(4^n)$ is that the correct way to say it? Basically I found that the second identity is true.

 

[evinda]

Here is what I've came up with..

I know that: $f(x) = O(g(x))$ iff $\exists$ positive constants $C$ and $n_0$ $|0 \le f(n) \le c * g(n),$ $\forall$ $n \ge n_0|$

So I found that $n! \notin O(4^n)$ by letting $n = 10$ and letting $c = 1$. Then I found that $4^n \in O(4^n)$ is that the correct way to say it? Basically I found that the second identity is true.

I agree that the second identity holds, but the first doesn't.
You can prove that $4^n=O(n!)$ as I did in my previous post.
I think that in order to prove that $n! \notin O(4^n)$ you have to show the negation of the definition you stated.
The negation of $\forall$ is $\exists$ and conversely. So you just have to find a $n$ such that the relation doesn't hold for any $c$.

 

[Evgeny.Makarov]

Then I found that $4^n \in O(4^n)$

This is trivially true because $f(n)\in O(f(n))$ for every $f$: just take $C=1$ and $n_0=0$.

The negation of $\forall$ is $\exists$ and conversely. So you just have to find a $n$ such that the relation doesn't hold for any $c$.

To elaborate on this, the definition of $f(n)\in O(g(n))$ says
\[
\exists C\,\exists n_0\forall n\ge n_0\;f(n)\le Cg(n).
\]
The negation of this is
\[
\forall C\,\forall n_0\,\exists n\ge n_0\;f(n)>Cg(n).
\]
So to prove that $n!\notin O(4^n)$ using the definition, you need to find an $n$ for every $C$ and $n_0$.