Search code examples
performancealgorithmasymptotic-complexity

the asymptotic growth of n choose floor(n/2)

How can I find the asymptotic growth of n choose floor(n/2) ? I tried to use the expansion and got that it is equal to 

[n*(n-1)*........*(floor(n/2)+1)] / (n-floor(n/2))!

Any idea how can i go from there? Any help is appreciated, prefer hints over answers

Solution

  • Using Stirling's approximation, you get

    n! = \sqrt{2n\pi}(n/e)^n

    If you substitute it into $\choose{n}{n/2}$, you should eventually end up with

    2^{n+1/2}/\sqrt{n\pi}

    PS. you might want to check my math before you actually use the answer :-)