# Proving Both Upper and Lower Bounds for Stirling's Approximation

• Comp Sci
• rxh140630
In summary, the conversation discusses the use of Stirling's approximation and the need to prove upper and lower bounds for the terms in the sum to establish its validity. The theta notation is also mentioned as a formal definition for proving the bounds.
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)$

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.

## What does "Prove lg(n) = thetha(nlgn)" mean?

"Prove lg(n) = thetha(nlgn)" is a statement in computer science that relates the logarithmic function (lg) to the logarithmic times linear function (thetha(nlgn)). It means that as the input size (n) increases, the time complexity of an algorithm with a logarithmic time complexity will also increase, but at a slower rate than an algorithm with a linearithmic time complexity.

## What is the significance of proving lg(n) = thetha(nlgn)?

Proving lg(n) = thetha(nlgn) is important in analyzing the time complexity of algorithms. It allows us to compare the efficiency of different algorithms and determine which one is more efficient for a given problem. It also helps in predicting the performance of an algorithm for larger input sizes.

## How is lg(n) = thetha(nlgn) proven?

To prove lg(n) = thetha(nlgn), we use mathematical techniques such as induction and asymptotic analysis. We first show that the algorithm has an upper bound of O(nlgn) and a lower bound of Ω(nlgn). This proves that the algorithm has a time complexity of thetha(nlgn).

## Can lg(n) = thetha(nlgn) be proven for all algorithms?

No, lg(n) = thetha(nlgn) can only be proven for algorithms with a time complexity of O(nlgn). It cannot be proven for algorithms with a lower time complexity, such as O(n) or O(n^2).

## What are some examples of algorithms with a time complexity of lg(n) = thetha(nlgn)?

Some examples of algorithms with a time complexity of lg(n) = thetha(nlgn) include binary search, merge sort, and heap sort. These algorithms have a logarithmic time complexity because they divide the input size in half at each step, resulting in a time complexity of O(lgn). However, they also have a linearithmic time complexity because they perform additional operations at each step, resulting in a time complexity of thetha(nlgn).

• Calculus and Beyond Homework Help
Replies
13
Views
922
• Precalculus Mathematics Homework Help
Replies
14
Views
789
Replies
24
Views
1K
• Quantum Physics
Replies
3
Views
1K
• Engineering and Comp Sci Homework Help
Replies
17
Views
668
• Calculus and Beyond Homework Help
Replies
7
Views
1K
• Calculus
Replies
4
Views
1K
Replies
1
Views
867
• Introductory Physics Homework Help
Replies
7
Views
382