3
$\begingroup$

The well-known algorithm for computing the $k$-th largest element in an unsorted array of size $n$ runs in $O(n)$ time.

How about for a range $[k, k+c]$, where $c$ is not necessarily independent of $n, k$? The obvious "brute-force" algorithm is to find the $k$th largest using the original $O(n)$-time algorithm, then the $k+1$-th largest the same way, ..., find the $k+c$-th largest (and also, the algorithm outputs these in sorted order). However, this takes $O(nc)$ time, and $c$ can possibly be $\Theta(n)$, which can lead to an $O(n^2)$ algorithm. In this case, we could have just sorted the array and extracted the elements, which takes $O(n \log n)$ time.

Is there a better (known) way of doing this? I can't find any references online.

$\endgroup$
2
$\begingroup$

Step 1. Use QuickSelect to find the $k$th largest number in the array. Call it $x$.

Step 2. Use QuickSelect to find the $k+c$th largest number in the array. Call it $y$.

Step 3. Find all elements in the array that are at least $x$ and at most $y$. This can be done by simply iterating over the array and comparing each element to $x$ and $y$.

Each step can be done in $O(n)$ time. Therefore, the total running time is $O(n)+O(n)+O(n) = O(n)$ time.

$\endgroup$
  • $\begingroup$ Thank you, I don't know why I couldn't see that, but it seems obvious now. $\endgroup$ – Bob Sep 29 '15 at 20:15

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.