Question

Show that $\mathbf{log}\left(n!\right)\mathbf{=}\mathbf{\theta }\left(\mathrm{nlogn}\right)$

(Hint: To show an upper bound, compare $\left(n!\right)$ with ${\mathbf{n}}^{\mathbf{n}}$. To show a lower bound, compare it with ${\left(\frac{n}{2}\right)}^{\frac{\mathbf{n}}{\mathbf{2}}}$).

Short answer

The statement $\log \left(\mathrm{n}!\right)=\mathrm{\theta }\left(\mathrm{nlogn}\right)$is proved.

Step-by-step solution

Explain Asymptotic notation.

Big O notation provides an asymptotic upper bound on a function, and omega notation provides an asymptotic lower bound. Three asymptotic notations are used to represent the time complexity of algorithms. They are: Big-O notation, Omega notation and Theta notation.

Prove the equation by upper bound.

The given equation is:

$\log \left(\mathrm{n}!\right)=\mathrm{\theta }\left(\mathrm{nlogn}\right)$

Let the right-hand side derivation be log(n!).

$$\begin{gathered} \log \left(\mathrm{n}!\right)=\log \left(1\times 2\times 3............\left(\mathrm{n}-1\right)\times \mathrm{n}\right) \\ \log \left(\mathrm{n}!\right)=\log 1+\log 2+\log 3..........+\mathrm{logn} \end{gathered}$$

From here, it is clear that $\log 1\le \mathrm{logn}$

$$\begin{gathered} \log \left(\mathrm{n}!\right)\le \mathrm{logn}+\mathrm{logn}+\mathrm{logn}.....+\mathrm{logn} \\ \log \left(\mathrm{n}!\right)\le \mathrm{nlogn} \end{gathered}$$

Prove the given equation by lower bound.

Now, prove for omega notation.

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

Let the left-hand side derivation be${\left(\mathrm{n}!\right)}^2$.

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

Here a quadratic equation is obtained, which is equal to data-custom-editor="chemistry" $\mathrm{f}\left(\mathrm{k}\right)$.

$\mathrm{f}\left(\mathrm{k}\right)=-\mathrm{k}+\mathrm{nk}+\mathrm{k}$where data-custom-editor="chemistry" $\left(1\le \mathrm{k}\le \mathrm{n}\right)$…….…(1)

Here, put the value of k in the equation (1).

$$\begin{gathered} \mathrm{f}{\left(\mathrm{k}\right)}_{\min }=-1^2+\mathrm{n}\times 1+1 \\ \mathrm{f}{\left(\mathrm{k}\right)}_{\min }=\mathrm{n} \end{gathered}$$

Equate both the equations:

$$\begin{gathered} {\left(n!\right)}^2=\prod _{k=1}^{n}f\left(k\right) \\ {\left(\mathrm{n}!\right)}^2\ge \prod _{\mathrm{k}=1}^{\mathrm{n}}\mathrm{f}{\left(\mathrm{k}\right)}_{\min } \\ {\left(\mathrm{n}!\right)}^2\ge \prod _{\mathrm{k}=1}^{\mathrm{n}}\mathrm{n} \\ {\left(\mathrm{n}!\right)}^2\ge {\mathrm{n}}^{\mathrm{n}} \end{gathered}$$

Taking $\log$on both sides:

$$\begin{gathered} \log {\left(\mathrm{n}!\right)}^2\ge \left(\log \right){\mathrm{n}}^{\mathrm{n}} \\ 2\log \left(\mathrm{n}!\right)\ge \mathrm{n}\left(\log \right)\mathrm{n} \\ \log \left(\mathrm{n}!\right)\ge \frac{\mathrm{n}}{2}\left(\log \right)\mathrm{n} \\ \log \left(\mathrm{n}!\right)\ge \mathrm{n}\left(\log \right)\mathrm{n} \end{gathered}$$

So, the final answer obtained is $\log \left(\mathrm{n}!\right)=\mathrm{\theta }\left(\mathrm{nlogn}\right)$

Hence data-custom-editor="chemistry" $\log \left(\mathrm{n}!\right)=\mathrm{\theta }\left(\mathrm{nlogn}\right)$is proved.