2
$\begingroup$

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? .

$\endgroup$
4
$\begingroup$

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$).

$\endgroup$
  • 3
    $\begingroup$ In other words $n = |V|$, and for constant $k$ this is polynomial time in $n$. $\endgroup$ – hardmath Mar 5 '13 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.