# Finding a lower bound for the expression \$log(n!)\$

Problem:
Is $$log(n!) in$$ $$Omega( n^n )$$?

Answer:
Since $$n! > n^n$$ for all $$n > 1$$ we can conclude that: $$log(n!) in$$ $$O( n^n )$$.
Let us look at the special case where $$n = 4$$.
begin{align*} n! &= 4(3)(2) = 24 \ n^n &= 4^4 = 256 end{align*}
Let us look at the special case where $$n = 5$$.
begin{align*} n! &= 5(4)(3)(2) = 5(24) = 120 \ n^n &= 5^5 = 3125 end{align*}
Let us look at the special case where $$n = 8$$.
begin{align*} n! &= 8! = 40320 \ n^n &= 8^8 = 16777216 end{align*}
It looks to me that $$n^n$$ is growing faster but that is not a proof. To prove it, I need to
show that there exists an $$M > 0$$ and $$n_o > 0$$ such that the following statement is true for
all $$n geq n_0$$:
$$n! leq M n^n$$
I select $$n_0 = 4$$ and $$M = 1$$. Hence the expression reduces to:
$$n! leq n^n$$
We have already shown that this expression is true for the special case of $$n = 4$$. Now, if we
add $$1$$ to $$n$$ we have:
$$(n+1)! leq (n+1)^{(n+1)}$$
This must be true because the left hand side increased by a factor
of $$n+1$$ and the right hand side increased by more than a factor of $$n+1$$. Now we add $$1$$ to $$n$$
again. The left hand side increases by a factor of $$n+2$$ and the right hand side increases by more
than a factor of $$n+2$$. Hence the right side increases more. We can repeat this process for ever. Therefore, I conclude the statement is true.
Do I have this right?