Simple question, given an input of size n, would an algorithm with runtime O(n choose (n/2)) = n!/((n/2)!(n/2)!), a.k.a. an algorithm which evaluates every possible partitioning of the input into two sets of equal size, be considered a polynomial time algorithm?
Asked
Active
Viewed 133 times
1
-
3Stirling's formula implies $\binom{n}{n/2} \sim \frac{2^n}{\sqrt{n\pi/2}}$, see here. – angryavian Nov 17 '22 at 18:50
-
... So no, it is not polynomial time. – David K Nov 17 '22 at 19:00
-
Without Stirling: $\frac{n!}{(n/2)!(n/2)!} = \frac{n}{n/2} \cdot \frac{n - 1}{n/2 - 1} \cdot \ldots \cdot \frac{n/2 + 1}{1} > 2^{n/2}$. – mihaild Nov 17 '22 at 19:28