Question

Show that is$\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{\text{is}}\mathbf{O}\mathbf{(}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{!}\mathbf{)}$

Short answer

By the definition of growth function and O-notation, $f\left(x\right)$is $\mathrm{O}\left(g\right(x\left)\right)$if there are constants C and k such that $\left|f\right(x\left)\right|\le C\left|g\right(x\left)\right|$whenever$x>k$ , it is proved that$n\log n$$\text{is}\mathrm{O}(\log n!)$

Step-by-step solution

Defining the definition of Growth function:

Consider f and g are functions from the set of integers or from the set of real numbers to the set of real numbers, we say that

By the definition of growth function and O-notation, $f\left(x\right)\text{is}\mathrm{O}\left(g\right(x\left)\right)$ if there are constants C and k such that $\left|f\right(x\left)\right|\le C\left|g\right(x\left)\right|\text{whenever}x>k$

Simplifying the factorial function:

We have,

$n!=n(n-1)(n-2)$

n! is bigger than or equal to all the terms, we can write,

$n!\ge n(n-1)\dots \dots \left(\frac{n}{2}\right)$

Since, all the terms are bigger than or equal to$\frac{n}{2}$ we have,

$n!\ge \left(\frac{n}{2}\right)\cdot \left(\frac{n}{2}\right)\cdots \left(\frac{n}{2}\right)$

Thus, we can write,

$n!\ge {\left(\frac{n}{2}\right)}^{\frac{n}{2}}$

Applying logarithm on both sides,

$\begin{array}{r}\log (n!)\ge \frac{n}{2}\log \left(\frac{n}{2}\right)\\ \ge \frac{n}{2}\log n-\frac{n}{2}\log 2\end{array}$

Thus, from the definition of O-notation, we can say that $n\log n\text{is}\mathrm{O}(\log n!)$ .