search
Log In
3 votes
792 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
edited by
792 views
1
Marked D. Is it correct?
2
yes
1
okay!!!
1
why not C)?
1
because in power $n+\frac{1}{2}=n$

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

this stackoverflow answer explains this problem very well. 

2 Answers

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.

edited by
0

@Verma Ashish

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

2

@srestha

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)

1
Constant does not have any effect in this case.becuz e^-ln2 does not have much contribution.

I think answers can be multiple but I have checked the answer key there Only D is the answer
0

But We Know already that Asymptotically [ 2^n == 2^(n+1) ] are same which is also, [ 2^n == 2*(2^n) ].

is this your contradiction to my doubt, that '2' is Constant and 'n' is not a constant?

0 votes
Answer:

Related questions

7 votes
5 answers
1
944 views
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $8$ $16$ $32$ $64$ None of the above
asked Dec 18, 2018 in Algorithms Arjun 944 views
2 votes
1 answer
2
334 views
A formula is said to be a $3$-CF-formula if it is a conjunction (i.e., an AND) of clauses, and each clause has at most $3$ literals. Analogously, a formula is said to be a $3$-DF-formula if it is a disjunction (i.e., an OR) of clauses of at most $3$ literals each. Define the ... $\text{3-DF-SAT}$ is NP-complete Neither $\text{3-CF-SAT}$ nor $\text{3-DF-SAT}$ are in P
asked Dec 18, 2018 in Algorithms Arjun 334 views
5 votes
4 answers
3
1.2k views
Asha and Lata play a game in which Lata first thinks of a natural number between $1$ and $1000$. Asha must find out that number by asking Lata questions, but Lata can only reply by saying Yes or no . Assume that Lata always tells the truth. What is the least number of ... ask within which she can always find out the number Lata has thought of? $10$ $32$ $100$ $999$ $\text{None of the above}$
asked Dec 18, 2018 in Algorithms Arjun 1.2k views
0 votes
1 answer
4
526 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
asked Dec 18, 2018 in Digital Logic Arjun 526 views
...