- #1

rxh140630

- 60

- 11

- 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: [itex]n! = \sqrt(2*pi*n)(\frac{n}{e})^n(1+ \theta{1/n}) [/itex]

Sterling's approximation: [itex]n! = \sqrt{2*pi*n}(\frac{n}{e})^n(1+ \theta(1/n)) [/itex]

So I need to prove

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

My question is:

assume I've proven [itex]lg(\sqrt{2*pi*n})[/itex] as [itex] \theta(lgn) [/itex]

Do I need to now prove that [itex] c_1nlgn ≤ lgn ≤ c_2nlgn [/itex] ??

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

Do I need to now prove that [itex] c_1nlgn ≤ \sqrt{n} ≤ c_2nlgn [/itex] ??

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

So I need to prove

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

My question is:

assume I've proven [itex]lg(\sqrt{2*pi*n})[/itex] as [itex] \theta(lgn) [/itex]

Do I need to now prove that [itex] c_1nlgn ≤ lgn ≤ c_2nlgn [/itex] ??

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

Do I need to now prove that [itex] c_1nlgn ≤ \sqrt{n} ≤ c_2nlgn [/itex] ??

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