edited by
3,350 views
10 votes
10 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!$ $?$

  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 by

2 Answers

18 votes
18 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.
edited by
Answer:

Related questions

11 votes
11 votes
5 answers
1
Arjun asked Dec 18, 2018
4,427 views
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$8$$16$$32$$64$None of the above
4 votes
4 votes
2 answers
3
Arjun asked Dec 18, 2018
4,148 views
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits ?$0.1$$0.2$$0.4$$0.5$All the above
5 votes
5 votes
1 answer
4