Question

Show that ${\mathbf{n}}^{\mathbf{n}}$is not.

Short answer

$n^n$is not$O(n!)$from theproof by contradiction.

Step-by-step solution

Definition of Big-O  Notation

Letfandgbe functions from the set of integers or the set of real numbers to the set of real numbers. We say that$f\left(x\right)$is$O\left(g\right(x\left)\right)$if there are constantscandksuch that

$\left|f\right(x\left)\right|\le C\left|g\right(x\left)\right|$

Whenever$x>k$

 To prove nn is not O(n!)

By the proof by contradiction,

Let assume$n^n$is $O(n!)$. Thenthere are constantscandksuch that

$\left|n^n\right|\le C|n!|$

Whenever$n>k$

Divide by$|n!|$on both sides,

$$\begin{gathered} \frac{\left|n^n\right|}{|n!|}\le \frac{C|n!|}{|n!|} \\ \frac{\left|n^n\right|}{|n!|}\le C \end{gathered}$$

Final Solution

Let $k>1$ for $n>1$, then,

$$\begin{gathered} \frac{n^n}{n!}=\frac{n}{n}\cdot \frac{n}{n-1}\cdot \dots \cdot \frac{n}{2}\cdot \frac{n}{1} \\ \ge 1\cdot 1\cdot \dots \cdot 1\cdot n \\ \frac{n^n}{n!}\ge \end{gathered}$$ ,

Now combing with the previous inequality we get,

$n\le \frac{n^n}{n!}\le C$

Here the function $f\left(n\right)=n$is not bounded as n is large.

Hence our assumption $n^n$is $O(n!)$is false.