I am reading Introduction to Algorithms 3rd for my CS course. Just before theorem 34.11 on pg 1087, it says the running time of the naive algorithm to try all k-subsets of $V$ is $\Omega(k^2(\binom{|V|}{k}))$ which is polynomial if $k$ is constant.
I don't understand this. How is $k^2\binom{|V|}{k} $ polynomial to $k$ (or $n$ whatever that is, I would think it's $|V| + |E|$, but not sure)?
For example, for $|V| = 8, k = 3$, $\binom{8}{k} = 56$, for $|V| = 100$, $k$ constant as $3$, $\binom{100}{k}$ = 161700. The binomial operation does not seem polynomial at all.
It is also unclear to me, what is $n$ here? .
Note that $\binom{n}{k} = \frac{n (n - 1) (n - 2) \ldots (n - k + 1)}{k!}$, which for a fixed $k$ is a polynomial in $n$ (of degree $k$).