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?