[Solved]: Kth largest subset for small K

Problem Detail: 

The $K$th Largest Subset problem is often given as an example of an NP-hard problem. However, the assumption is that $K$ is unconstrained, and can be as large as $2^n$. Clearly, if $K \le 3$ the solution in $O(n)$ time is trivial.

Are there any general results for time complexity of this problem for a given (and potentially small) $K$?

Asked By : MaxB

Answered By : Yuval Filmus

There is a simple algorithm whose complexity is $O(Kn)$. The algorithm computes, for each $m \leq n$, the $K$ largest sums of the first $m$ numbers. Given the list for $m$, the list for $m+1$ is computed by adding the $(m+1)$st element to the old list, merging the two lists, and keeping only the top half. Since merging sorted lists can be done in linear time, the resulting complexity is $O(Kn)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/36005

 Ask a Question

 Download Related Notes/Documents