Prove lg(n!) = thetha(nlgn)

  • Comp Sci
  • Thread starter rxh140630
  • Start date
  • #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]
 

Answers and Replies

  • #2
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,321
The upper and lower bounds of Stirling's formula are so good, that I would use both of them just to be on the safe side.
$$
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}
$$

The formal definition of the theta notation is:
$$
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
$$
so, yes, you have to manage both ends.
 

Suggested for: Prove lg(n!) = thetha(nlgn)

  • Last Post
Replies
1
Views
704
  • Last Post
Replies
12
Views
736
  • Last Post
Replies
2
Views
557
  • Last Post
Replies
7
Views
392
Replies
4
Views
347
Replies
5
Views
1K
  • Last Post
Replies
2
Views
853
Top