Marked D. Is it correct?

The Gateway to Computer Science Excellence

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

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,291 answers

198,209 comments

104,889 users