The Gateway to Computer Science Excellence
0 votes
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})$
in Algorithms by Veteran (431k points)
edited by | 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. 

2 Answers

+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.
by Boss (12.9k points)
edited by
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)$

0 votes
by Junior (775 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,209 comments
104,889 users