0
$\begingroup$

I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of size n.

However, I am not sure whether this can be done in polynomial time or not.

$\endgroup$
2
$\begingroup$

For fixed $k$, the running time is polynomial, but if $k$ is part of the input, the running time is not polynomial. The number of such subsets is ${n \choose k}$, which is very roughly like $n^k$. Thus, if $k$ is fixed to something like 3, this becomes $O(n^3)$ -- polynomial. However, if $k$ is part of the input, the running time is exponential in $k$.

$\endgroup$
  • $\begingroup$ Finding the answer to the problem of finding all subsets of size k seems to be linear in the size of the output, which is the best one can expect. I'm not sure if I would call this kind of problem with enormous output size "hard". $\endgroup$ – gnasher729 Feb 17 at 0:12
  • 1
    $\begingroup$ @gnasher729, absolutely. However, the standard convention is that the running time of an algorithm is normally measured as a function of the input size not the output size, unless otherwise specified. In particular, "polynomial time", without any further caveats, is normally understood to mean polynomial in the size of the input. $\endgroup$ – D.W. Feb 17 at 0:14

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.