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

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

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?

– user114966
Apr 1 at 22:08
• At the beginning of your question you are asking about a lower bound, but in the rest of the question you are talking about an upper bound? Apr 1 at 22:08
• @Dmitry I do not currently have an instructor. I am not currently taking a course.
– Bob
Apr 1 at 22:18
• @Steven I realize that the line $n! > n^n$ is wrong. It was a mathematical typesetting error. I should have written $n! < n^n$. I am thinking I need to be very carefully in updating the post due to the comments already made.
– Bob
Apr 1 at 22:22

Firstly, $$n!$$ is NOT greater than $$n^n$$. Indeed, $$n! = \displaystyle\prod\limits_{k=1}^nk\leq \prod\limits_{k=1}^nn = n^n$$.
Secondly, even if you have a function $$f(n)$$ such that $$f(n) > n^n$$, that does not mean that $$\log(f(n)) \in \Omega(n^n)$$. For example, $$n^{n+1}>n^n$$, but $$\log(n^{n+1}) = (n+1)\log n < n^2 = o(n^n)$$.
Finaly, you can write $$\log(n!) = \log(\prod\limits_{k=1}^nk) = \sum\limits_{k=1}^n\log(k) \leq \sum\limits_{k=1}^n\log(n) = n\log n$$.
With this inequality, we can deduce that $$\log(n!) \in O(n\log n)$$ and since $$n\log n = o(n^n)$$, the statement $$\log(n!) \in \Omega(n^n)$$ is false.
$$\log n! \le \log n^n = n \log n = o(n^n)$$.