2
$\begingroup$

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.

  • 0
    Well, it is true that the left hand side is both $n^{-O(n)}$ and $n^{-\Omega(n)}$, if that is your confusion.2011-09-20

1 Answers 1

2

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.

  • 1
    yeah right I forgot this good old $$n$=e^{\$l$og $n$}$ tra$n$s$f$ormation, otherwise it's all quite clear.2011-09-20