Finding a lower bound for the expression $\log(n!)$ Problem:
Is $\log(n!) \in$ $\Omega( n^n )$?
Answer:
Since $n! &gt; n^n$ for all $n &gt; 1$ we can conclude that: $\log(n!) \in$ $O( n^n )$.
Let us look at the special case where $n = 4$.
\begin{align*}
n! &amp;= 4(3)(2) = 24 \\
n^n &amp;= 4^4 = 256
\end{align*}
Let us look at the special case where $n = 5$.
\begin{align*}
n! &amp;= 5(4)(3)(2) = 5(24) = 120 \\
n^n &amp;= 5^5 = 3125
\end{align*}
Let us look at the special case where $n = 8$.
\begin{align*}
n! &amp;= 8! = 40320 \\
n^n &amp;= 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 &gt; 0$ and $n_o &gt; 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?
$\log n! \le \log n^n = n \log n = o(n^n)$.