3 votes

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!$ $?$

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

8 votes

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)$

Option (D) is the answer.

$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)$

Option (D) is the answer.

2

They are not asymptomatically same..

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

3

What about E?

here my soln

from the range we can write:

n! = theta(n^(n+1/2) x e^-n)

now

we know that

2^n = e^nln2

so, 2^-n = e^-nln2 neglecting ln2 as it is a constant

replace this e^-n with 2^-n

finally,

**n! = theta(n^(n+1/2) x 2^-n)**

that's the option E.

and

D is also correct.

**why they had written " what are the asymptotic bounds...." in the question ,that means multiple solution possible?**

0

@shaktisingh you seems correct..

but in my opinion removing constant from power is not a good choice...

$2^n=3^{n\log_32}$

after removing $log_32$, 2^n=O(3^n) but 2^n can't be theta(3^n)