# How is naive CLIQUE algorithm polynomial time?

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$).
• In other words $n = |V|$, and for constant $k$ this is polynomial time in $n$. – hardmath Mar 5 '13 at 23:47