0
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Please check this: cs.meta.stackexchange.com/questions/597/…. Asking others to check your work is not what this site for (ask your instructor if you have one). If you are not sure about a specific step, please specify it (and why you are not sure about it). $\endgroup$
    – user114966
    Apr 1 at 22:08
  • $\begingroup$ 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? $\endgroup$
    – Steven
    Apr 1 at 22:08
  • $\begingroup$ @Dmitry I do not currently have an instructor. I am not currently taking a course. $\endgroup$
    – Bob
    Apr 1 at 22:18
  • $\begingroup$ @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. $\endgroup$
    – Bob
    Apr 1 at 22:22
0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\log n! \le \log n^n = n \log n = o(n^n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.