Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I saw this in Wegener(2003), Methods for the Analysis of Evolutionary Algorithms as a upper bound on the probability.

After applying Stirling approximation to $(\frac{n}{3})!$ I still keep getting something like $O(n^{-n+ \epsilon})$. The paper does not offer any additional derivation details, so I wonder if some1 could help me out with this.

share|improve this question
    
Well, it is true that the left hand side is both $n^{-O(n)}$ and $n^{-\Omega(n)}$, if that is your confusion. –  Srivatsan Sep 20 '11 at 3:42

1 Answer 1

up vote 2 down vote accepted

We can, of course, use Stirling's approximation, but given that the claim is quite loose, we can get away with an even more elementary bound; namely, $k! \geq k^{k/2}$. Using this, $$ \Big(\frac{n}{3} \Big)! \geq \Big(\frac{n}{3} \Big)^{n/6} = n^{n/12} \Big(\frac{n}{9} \Big)^{n/12} \geq n^{n/12} = \exp\left(\frac{1}{12} n \log n \right), $$ for $n \geq 9$. We get the claim by taking reciprocals.

share|improve this answer
1  
yeah right I forgot this good old $n=e^{\log n}$ transformation, otherwise it's all quite clear. –  sigma.z.1980 Sep 20 '11 at 3:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.