369 views

Stirling’s approximation for $n!$ states for some constants $c_1,c_2$

$$c_1 n^{n+\frac{1}{2}}e^{-n} \leq n! \leq c_2 n^{n+\frac{1}{2}}e^{-n}.$$

What are the tightest asymptotic bounds that can be placed on $n!$ $?$

1. $n! = \Omega(n^n) \text{ and } n! = \mathcal{O}(n^{n+\frac{1}{2}})$
2. $n! = \Theta(n^{n+\frac{1}{2}})$
3. $n! =\Theta((\frac{n}{e})^n)$
4. $n! =\Theta((\frac{n}{e})^{n+\frac{1}{2}})$
5. $n! =\Theta(n^{n+\frac{1}{2}}2^{-n})$

edited | 369 views
0
Marked D. Is it correct?
+1
yes
0
okay!!!
+1
why not C)?
0
because in power $n+\frac{1}{2}=n$

right?
0
why not E ??? anyone ??
+1
0

this stackoverflow answer explains this problem very well.

+1 vote
Given that -

$c_1n^{n+\frac{1}{2}}e^{-n}\leq n!\leq c_2n^{n+\frac{1}{2}}e^{-n}$.

$n!=\Theta\left(\frac{n^{n+1/2}}{e^n}\right)$

We can divide it by $e^{1/2}$  (multiplying or dividing by a +ve constant doesn't affect the asymptotic nature of a function)

$\implies n!=\Theta\left(\frac{n^{n+1/2}}{e^{n+1/2}}\right)=\Theta\left(\left(\frac{n}{e}\right)^{n+\frac{1}{2}}\right)$

by Boss (12.9k points)
edited
0

@Verma Ashish

C) and D) asymptotically same, na? Then why not C) too ans?

+1

@srestha

They are not asymptomatically same..

$n^n$ vs $n^{n+1/2}$ , $n^{n+1/2}$ is $\theta (n^n\times \sqrt n)$