Does $\binom{n}{k}$ additions or XORs run in polynomial time?

Question

If $O(\binom{n}{k})$ = $O(min(n^k, n^{n-k}))$, does that mean a function that runs $\binom{n}{k}$ iterations (e.g. additions, XORs) runs in polynomial time?

I keep arguing myself in circles whether it does or not.

Answer 1

There are two parameters here, $n$ and $k$. So you can't just say that the algorithm runs in polynomial time unless you can say what it's polynomial in. Although it's hard to say that it's polynomial in $k$ because $k$ is restricted to being no greater than $n$, so you can't just let $k$ go to infinity on its own.

For any constant value of $k$, it is true that ${n \choose k} = O(n^k)$, and so the algorithm is polynomial in $n$.

Similarly, for any constant difference $n - k = m$, it's true that ${n \choose k} = O(n^m)$, and so the algorithm is again polynomial in $n$.

However, consider what happens if we're always at the midpoint - so $k = \lfloor \frac{n}{2} \rfloor$. In this case ${n \choose k} = O(n^{\frac{n}{2}}) = O(\exp(\frac{n}{2}\log n))$ which is factorial complexity.