2

I am trying to prove that $\log(n!)$ is $O(\log n^n)$ and I have an intuition for it, but I can't seem to find the constant $c$ that would make $\log(n!) < c \cdot \log(n^n)$ for all $n > n_0$.

As of now my idea is that we could split $\log(n!)$ into $\log(1) + \log(2) + \dots + \log(n)$ and $\log(n^n)$ into a sum of $n \log(n)$s, but I still don't think that would give me a constant $c$ that doesn't depend on $n$. Could you all guide me in the right direction?

Jan
  • 5,552
  • 10
  • 19
  • 31
dl2022
  • 21

1 Answers1

4

For $n>1$ we have $n! < n^n$. Since $\log n$ is increasing it follows $\log(n!) < \log(n^n)$ and so the constant $c=1$ is enough.

To prove $n!< n^n$ just write $$ n! = 1 \cdot 2 \cdot \ldots \cdot n \le n \cdot n \cdot \ldots \cdot n = n^n.$$

Daron
  • 10,300