Question

Determine whether $\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{!}$is$\mathbf{\Theta }\mathbf{(}\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{)}$ . Justify your answer.

Short answer

Since, the function $\log n!$satisfies both the conditions,

$$\begin{gathered} \log (n!)=\mathrm{O}(n\log n)AND \\ \log (n!)=\mathrm{O}(n\log n) \end{gathered}$$

Then we can write $\log n!\text{is}\mathrm{\Theta }(n\log n)$.

Step-by-step solution

Proving the first condition log⁡(n!)=O(nlog⁡n) :

Consider$f\left(x\right)=\log n!$

$\begin{array}{r}\log n!=\log (\mathrm{1.2.3}\dots \dots (n-1\left)n\right)\\ =\log 1+\log 2+\log 3+\dots ..+\log n\end{array}$

Since, all the log terms are lesser than or equal to

So, we can write,

$\log 1+\log 2+\log 3+\dots .+\log n=n\log n$

Since, n is greater than n! ,

$\log n!\le n\log n$

Therefore, by the definition of O-notation we can say that

$\log (n!)=\mathrm{O}(n\log n)$

Proving the second condition log⁡(n!)=Ω(nlog⁡n) :

The factorial function$(n!{)}^2$ cab written as,

$\begin{array}{r}(n!{)}^2=n!\times n!\\ =(\mathrm{n}\times 1)\left(\right(\mathrm{n}-1)\times 2)\left(\right(\mathrm{n}-2)\times 3)\dots .(1\times \mathrm{n})\\ =\prod _{\mathrm{k}=1}^{\mathrm{n}} (\mathrm{n}-\mathrm{k}+1)\mathrm{k}\\ =\prod _{\mathrm{k}=1}^n \left(-{\mathrm{k}}^2+\mathrm{nk}+\mathrm{k}\right)\end{array}$

Consider$F\left(k\right)=-k^2+nk+k$ where$1\le k\le n$

$F\left(k\right)$is minimum when K + 1

So,$F\left(1\right)=n$

Thus, we can write as,

$\begin{array}{r}(n!{)}^2=\prod _{k=1}^n F(k)\ge \prod _{k=1}^n F(k{)}_{min}\\ \Rightarrow (n!{)}^2\ge \prod _{k=1}^n n\\ \Rightarrow (n!{)}^2\ge n^n\end{array}$

Applying logarithm on both sides

$\begin{array}{r}2\log n!\ge n\log n\\ \Rightarrow \log n!\ge \frac{1}{2}n\log n\end{array}$

Therefore, by the definition of O-notation, we can say that

$\log (n!)=\mathrm{\Omega }(n\log n)$

Hence, from these conditions, it is proved that $\log n!\text{is}\mathrm{\Theta }(n\log n)$