# Prove lg(n!) = thetha(nlgn)

• Comp Sci
rxh140630
Homework Statement:
prove lg(n!) = thetha(nlgn) where lg n is log with base = 2. Use Sterling's approximation as a hint
Relevant Equations:
Sterling's approximation: $n! = \sqrt(2*pi*n)(\frac{n}{e})^n(1+ \theta{1/n})$
Sterling's approximation: $n! = \sqrt{2*pi*n}(\frac{n}{e})^n(1+ \theta(1/n))$

So I need to prove

$c_1nlgn ≤lg(\sqrt{2*pi*n}) + lg((\frac{n}{e})^n) + lg(1+ \theta(1/n))) ≤ c_2nlgn$

My question is:

assume I've proven $lg(\sqrt{2*pi*n})$ as $\theta(lgn)$

Do I need to now prove that $c_1nlgn ≤ lgn ≤ c_2nlgn$ ??

What if we assume I found that $lg(\sqrt{2*pi*n})$ as $\theta(\sqrt{n})$

Do I need to now prove that $c_1nlgn ≤ \sqrt{n} ≤ c_2nlgn$ ??

Assuming the other terms in the sum $g(\sqrt{2*pi*n}) + lg((\frac{n}{e})^n) + lg(1+ \theta(1/n)))$ are proven to be $\theta(nlgn)$

$$1< e^{1/(12n+1)} < \dfrac{n!}{\sqrt{2\pi n}\cdot\left(\dfrac{n}{e}\right)^n} < e^{(1/12n)}< 1+\dfrac{1}{11n}$$
$$f(x)=\theta(g(x)) \Longleftrightarrow 0<\operatorname{lim\,inf}_{x\to a}\left|\dfrac{f(x)}{g(x)}\right|\leq \operatorname{lim\,sup}_{x\to a}\left|\dfrac{f(x)}{g(x)}\right|<\infty$$