Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer
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


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.