2
$\begingroup$

I'm given a set of $n$ numbers. Is there a data structure that builds in $O(n)$ (linear time) and gets the $k$'th largest element in $O(k)$ time? Also, is there anything better than $O(k)$?

$\endgroup$
  • 2
    $\begingroup$ Welcome to Computer Science! Your question looks like interesting. If it comes from an online course or contest or article, please add a URL in the question. If it comes from a book or a paper, a reference. Besides paying proper attribute to the original source, all that information motivates and helps more people answer your question faster and better. $\endgroup$ – Apass.Jack Oct 30 '18 at 10:29
  • 2
    $\begingroup$ I just noticed that you have not accepted any answer for all your 7 questions at Stackoverflow. It looks like you are not aware that you can accept an answer if you are the questioner. It is part of a basic protocol and etiquette to try accepting the best answer that has answered your question by clicking on the check mark beside the answer to toggle it from greyed out to filled in. You can check the FAQ entry on when someone answers. You can also check how important is accepting an answer. $\endgroup$ – Apass.Jack Oct 30 '18 at 11:10
  • $\begingroup$ The closest I can think of is an array, where randomised selection works in $O(n)$ on an average (although it's $O(n^2)$ in the worst case), and takes $O(n)$ to build too. However, I too am interested, if something like this does exist. $\endgroup$ – Gokul Oct 30 '18 at 15:27
  • $\begingroup$ @Gokul There is a well-known selection algorithm working in linear time. Also, the problem can be solved as stated, quite easily. $\endgroup$ – Yuval Filmus Dec 29 '18 at 21:48
3
$\begingroup$

Here is a solution that uses only comparisons. For simplicity, assume that $n$ is a power of 2.

Find the median of the original array in $O(n)$, and extract the largest $n/2$ elements. Then find the median of the new array in $O(n/2)$, and extract the largest $n/4$ elements. Continue in this way, extracting the $n/8,n/16,\ldots,1$ largest elements. In total, preprocessing takes time $$ O(n+n/2+n/4+\cdots) = O(2n) = O(n). $$

Given $k$, find $\ell$ such that $n/2^{\ell+1} < k \leq n/2^{\ell}$. By construction, $n/2^\ell < 2k$. The $k$th largest element is thus one of the $n/2^{\ell}$ largest elements. Using the linear time selection algorithm, locate the $k$th element among them in $O(n/2^\ell) = O(k)$.


We can improve the running time for $k \leq Cn/\log n$ (for arbitrary $C$) to $O(1)$ as follows.

During preprocessing, use a linear time selection algorithm to locate the $Cn/\log n$-th largest element in $O(n)$, and extract all larger elements. Sort them in $O(n)$.

During query time, locate the $k$th largest element for $k \leq Cn/\log n$ in $O(1)$ using the new array.

Conversely, we can show that this $O(1)$ behavior cannot extend beyond $O(n/\log n)$ for comparison-based algorithms. Indeed, suppose that there is an algorithm which preprocesses an array in $O(n)$, and is able to locate the $k$th element in $O(1)$ for $k \leq f(n)$, where $f(n) = \omega(n/\log n)$. This allows us to sort an array of size $f(n)$ in time $O(n) + O(f(n)) = o(f(n) \log f(n))$ by adding $n - f(n)$ dummy elements, contradicting the well-known lower bound for sorting.

$\endgroup$
0
$\begingroup$

If you can apply Radix sort, just sort the data and you are done.

If you only can compare data, then such algorithm can be used to find arbitrary element of sorted sequence in O(N), while it was proved that such sorting requires O(n*log(N)).

So, no way.

$\endgroup$
  • 1
    $\begingroup$ That is mostly true, but since you said these are integers, if you know beforehand the number of valid values (say, numbers between 1 and 100), you can use counting sort, which is bound by the number of valid values(|S|), and can run at O(n*|S|) which can be useful sometimes. $\endgroup$ – Daniel Dubovski Oct 30 '18 at 16:37
  • $\begingroup$ @DanielDubovski, you are right - i missed that question asks specifically about "numbers". So if each number occupies fixed number of cells, then radix sort is possible and requires only O(n^epsilon) extra space. Counting sort is a bit worse since it requires O(n) extra space. $\endgroup$ – Bulat Oct 30 '18 at 19:13
  • $\begingroup$ Selection (finding the $k$th largest element, for given $k$) can be done in linear time. In particular, your lower bound doesn't work. Indeed, such an algorithm does exist. $\endgroup$ – Yuval Filmus Dec 29 '18 at 21:47
0
$\begingroup$

Since these are numbers, we can sort them with Radix Sort in O(N) time and then find k'th largest element in O(1) time.

Extra memory required for radix sort is O(n^epsilon) where epsilon may be any positive number up to 1.

$\endgroup$
-2
$\begingroup$

I don't think there is such algorithm. If there was, you would be able to find median in O(n) which is AFAIK unknown or even it is proven it doesn't exist.

$\endgroup$
  • 1
    $\begingroup$ There are algorithms to find median in $O(n)$. $\endgroup$ – Apass.Jack Oct 30 '18 at 15:58
  • $\begingroup$ Could you please post the source? $\endgroup$ – smrt28 Oct 30 '18 at 16:01
  • $\begingroup$ You can check my answer to median of medians: bound on pivot position $\endgroup$ – Apass.Jack Oct 30 '18 at 16:07
  • $\begingroup$ Median of medians finds just an approximate median. $\endgroup$ – smrt28 Oct 30 '18 at 16:28
  • $\begingroup$ It looks like you have misled by the Wikipedia entry on median of median that says conspicuously "the median of medians is an approximate (median) selection algorithm". That very confusing or simply wrong statement will be corrected or clarified soon or later. (In fact, somebody said in Wikipedia talk that misleading part of the Wikipedia "seems to have been introduced by a user without an account named Harish Victory back in June 2017".) $\endgroup$ – Apass.Jack Oct 30 '18 at 21:39

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.