I just finished the implementation of an algorithm and wanted to report its approximate run-time in a O*($c^n$) format, the time analysis results is O*$n/2 \choose n/4$. I'm using the binary entropy function.
O*$n/2 \choose n/4$ $\approx$ O*($2^{\frac n 2 H(1/4)}$) $\approx$ O*($2^{\frac n 2 0.811}$) $\approx$ O*($1.324^n$)
Should I do this in a different way to do this accurately?
If you use the Stirling's approximation in the expression of the binomial O${n/2} \choose {n/4} $ for every factorial you come up with asymptotic complexity: $$ \frac{2^{n/2}}{\sqrt{n}} $$ This is not asymptotic to any expression of type $c^n$. This would anyway be a very good form for the reported asymptotic limit.
Indeed, if you use the fact proved in this question (which I guess is what you used to get to your result), you obtain that $$ {n/2 \choose n/4 } \sim 2^{(H(1/2)^{2n})} $$ which is different from what you stated (you can't bring the exponent of $H$ down as exponent of $2$).
