$O(\frac{n!}{(\frac{n}{2}!)^2})$ is polynomial complexity?

Question

$O(\frac{n!}{(\frac{n}{2}!)^2})$ is polynomial complexity?

Can anyone prove it or disprove it? (If it is polynomial complexity, what is the degree?

Answer 1

As Wojowu commented, Stirling approximation is the tool $$A=\frac{n!}{(\frac{n}{2}!)^2}\implies \log(A)=\log(n!)-2\log\left(\frac{n}{2}!\right)$$ Now, for large $p$ $$\log(p!)=p (\log (p)-1)+\frac{1}{2} \left(\log (2 \pi )+\log \left({p}\right)\right)+\frac{1}{12 p}+O\left(\frac{1}{p^3}\right)$$ making $$\log(A)=n \log (2)+\frac{1}{2} \log \left(\frac{2}{\pi n}\right)-\frac{1}{4 n}+O\left(\frac{1}{n^3}\right)$$ Then $$A=e^{\log(A)}= ???$$

Answer 2

You don't need anything fancy here. Note that $$(2j+1)(2j)>4j^2;$$this shows that $$(2n+1)!>4^n (n!)^2.$$(For example, $$7!>6(6)(4)(4)(2)(2)=4^3 (3!)^2.)$$