# Finding the greatest $k$ numbers with a certainty of $p$

Given $n \in \mathbb{N}$ pairwise distinct numbers. I want to do as few comparisons per number as possible - and every number should experience roughly the same amount of comparisons as another number - and find the greatest $k \leq n$ numbers, e.g. $k = \frac{n}{10}$. In order to minimise the number of comparisons per number, I allow an error, say I am okay if I know that the result is correct with only a probability of $p$.

I study mathematics and only had a very shallow introduction to algorithms so far, and the only relevant algorithms we discussed would be sorting algorithms. QuickSort comes to mind, but firstly I am not sure how I would implement my "tolerance of an error" and secondly, I think the fact that I only need the greatest $k$ numbers and I don't want to sort them, there might be more efficient algorithms.

Any basic approach would be a great help already, I'll gladly do the maths on my own.

Thanks in advance for any help.

-
You can find the $k$ greatest numbers with 100% accuracy in $O(n)$ time, as answered below. Is it worth some chance of error to do a little bit better than that? –  usul Dec 12 '12 at 18:16
@usul: I don't know how much better one can get if say I only want 90% accuracy. That's why I asked. –  Huy Dec 12 '12 at 18:58
Well, if you want e.g. the highest $\frac{n}{10}$, you'll still need $O(n)$ time, so you'll just get a better constant. You also might have to think about what you mean by % accuracy. Is it that, on any input, your algorithm is guaranteed to get 90% of the top $k$ items in its list? Is it that, on any input, your randomized algorithm gets in expectation 90% of the top $k$ items in its list? Is it that, on a random input, your deterministic algorithm gets 90%? Etc. –  usul Dec 12 '12 at 19:05
I'm sorry, I really am not very experienced with this topic but the second version sounds best. I didn't know I can only get a better constant, but now I do. :) –  Huy Dec 12 '12 at 19:39
Right, the reason being that if you want the top $\frac{n}{10}$ items, then your output is of size $\frac{n}{10} \in O(n)$ already. Also, if you wanted to guarantee 90% accuracy, you would have to check at least 90% of the input, which is $0.9n \in O(n)$. But with the randomized maybe you can do a bit better. Anyway, hope this is helpful! Half the battle in finding an answer to something is nailing down the question you want to ask. –  usul Dec 12 '12 at 19:53

I propose the following algorithm. You take some random element $p$ of your input as pivot element for $k=n/10$. Next, you scan through all your data and split it into a list of elements $\le p$ and a list with elements $>p$.

Case 1: The list with the larger elements contains more then $k$ elements. Then take this list and repeat.
Case 2: The list with the larger elements contains less than $k$ elements, say $m$. The repeat with the other list, but set $k=k-m$.
Case 3: Otherwise you are done.

This is very easy to implement and should find the solution quickly. (You said you want to do the math by yourself ;) )

Remark: There is a classic $O(n)$ algorithm for this. You can determine the $k$-th biggest element in $O(n)$ by the algorithm of Blum et al. and then use this element as pivot. However, I think the the constant in the $O(n)$ makes this variant slower then the above solution. Especially if you are fine with an imprecise solution.

-
it seems fair to point out that this is basically the well known quickselect algorithm. it runs in O(n) expected running time, and is always correct, although (with small probability) can be slow. the five people algorithm is indeed slower in practice. its virtue is being deterministic –  Sasho Nikolov Dec 12 '12 at 18:21
@SashoNikolov: I wasn't aware that this is know as quickselect. Thanks for the pointer. –  A.Schulz Dec 12 '12 at 18:32

Use the selection algorithm to find the $k$th greatest element, and then run through your set of numbers to keep only the elements greater than this $k$th element.

The time complexity of this algorithm is $O(n)$. This means that there is a constant $c$ such that the number of comparisons and the number of computation steps are eventually bounded by $cn$ where $n$ is the number of elements.

-
Note: this works with $p=1$, but I don't know how to make the algorithm faster if $p<1$. –  jmad Dec 12 '12 at 18:10
Can you possibly get better than $O(n)$? Ah, you mean improve on the constant I suppose. –  Realz Slaw Dec 12 '12 at 18:12
Considering that comparisons aren't actually constant-time, perhaps the selection algorithm isn't actually $O(n)$? If so, it can improved on that by using a probabilistic comparison of some sort. Or does the OP want only a reduction in the number of comparisons? –  Realz Slaw Dec 12 '12 at 18:14
@RealzSlaw: I don't know, finding better such constant bounds (it is necessary to have $O(n)$ comparisons at least if $p$ is not too small) seems difficult and is arguably worth the effort. –  jmad Dec 12 '12 at 18:59

Here's something more complicated, which performs $n + o(n)$ comparisons, and achieves an approximately correct list with high probability.

Suppose you want to partition a set $V$ of $n$ elements into a disjoint union $L \cup S$ of a set of larger elements and a set of smaller elements, where every $s \in S$ is bounded above by every $\ell \in L$, and where where $\# L \approx \sigma n$ for some constant $0 < \sigma < 1$. Then with only a constant (or smaller than constant) probability of failure, we can select $L$ in such a way that it contains all of the $\sigma n$ largest elements of $V$, together with only a constant (or decreasing) fraction of extraneous elements.

### Algorithm

1. Obtain a sample $X$ of $N$ randomly selected elements, for some $0 < N < n$ which we will specify later. Sort them. This takes time $O(N \log(N))$.

2. For some parameter $\delta > 0$, find a pivot $x^\ast$, chosen to be the $(\sigma + \delta/2) N^{\text{th}}$  largest element of $X$. (If there are multiple elements with the same value, put all of the copies of the value of $x^\ast$ which precedes the $(\sigma + \delta) N^{\text{th}}$ largest element into $L$; put the rest of the values, including $x^\ast$ itself, into $S$.)

3. Compare all of the remaining elements of $V \smallsetminus X$ to $x^\ast$. If they are larger, put them in $L$; otherwise, put them in $S$.

Let $M$ be the set of the $\sigma n$ largest elements of $V$. We will consider the probability that $L$ contains all of the elements of $V$, but no more than $\delta n$ additional elements of $V$ beyond that.

### Probabilistic and run-time analysis.

The probability that any particular element of $X$ is in $M$ is, by definition, $\sigma$. In particular, by the Hoeffding bound, the probability that $X$ contains as many as $(\sigma + \delta/2)N$ elements of $M$ scales as $$\Pr\biggl[ \#(X \cap M) \geqslant (\sigma + \delta)N \biggr] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr),$$ and that therefore $$\Pr\biggl[ x^\ast \in X \cap M \biggr] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr).$$ Because $L$ is constructed to be all of the values which are larger (or at least succeed) $x^\ast$ in $V$, it follows that $M$ is a subset of $L$ provided that $x^\ast \notin M$. Then, we have $$\Pr\biggl[ M \not\subseteq L \biggr] ~~\leqslant~~ \exp\Bigl( -\delta^2 N/2\Bigr),$$ for any $\delta > 0$. We want more than this, however: we would like the number of extraneous elements in $L$ not to be too large. The expected number of elements in $L$ is going to be $(\sigma + \delta/2)n$, but we're interested in the probability with which it is less than $(\sigma + \delta)n$, as well as being at least $\sigma n$. That is, we want to know the probability with which the number of elements is bounded by $\delta n/2$ from the expected value, which is $$\Pr\biggl[ |\# L - \sigma n | \geqslant \delta/2 \biggr] ~~\leqslant~~ 2 \exp\Bigl( -\delta^2 N/2\Bigr).$$ If we want this probability of failure to be at most some value $0 < p < 1$, we then require $$$$p \geqslant 2\exp\Bigl( -\delta^2 N/2\Bigr) ~~\implies~~ N \geqslant \frac{2\ln(2/p)}{\delta^2}\;.$$$$ If we choose $N$ to be at least this large, then with probability $(1-p)$, the set $L$ will contain all of the elements of $M$, but no more than $\delta n$ elements more than that — it will be a modest overestimate of the set $M$.

The above also holds if $p$ or $\delta$ are decreasing functions of $n$, so that the notion of just how modest an overesitmate $L$ is, or how high a probability of success we can achieve, can be tuned to a limited extent. However, in order to compete with the deterministic, linear-time selection procedures, we require the sort-time of the set $X$ to be $o(n)$. If we set $N = \bigl\lceil \ln(1/p)/2\delta^2 \bigr\rceil$, we then have $$O(N \log(N)) ~=~ O\left( \log(1/p) \delta^{-2} \Bigl[ \log \log(1/p) + \log(1/\delta) \Bigr] \right) ~\subseteq~ o(n) .$$ The remaining run-time is taken up by comparisons of the other elements of $V$ with the pivot $x^\ast$, which is an unavoidable overhead, but is at most $n$ comparisons. Then there are a total of $n - N + O(N \log (N)) = n + o(n)$ comparisons made, where $x^\ast$ is subject to the most comparisons (at most $n + o(n)$ comparisons), all of the other $N-1$ elements of $X$ are subject to at most $N \in o(n/\log(n))$ comparisons each, and every remaining element is compared only once.

### Examples & Remarks.

If we're content to achieve a constant but small probability of failure $0 < p \ll 1$, and overestimate by some constant fraction $0 < \delta < 1$ of the elements of $V$, then the bound on $N$ gives us some constant size of sample which is enough to achieve this; this gives the smallest possible number of comparisons, $n + \theta(1)$, and also where the number of comparisons is closest to being uniform for all elements. For other cases, where we only require $N \log(N) \in o(n)$, here is a range of possibilities.

Suppose that we wanted to have the probability of success increase with $n$, for instance $1/p \in O(n^t)$ for some fixed $t > 0$. To have $N \log(N) \in o(n)$, we require $$t \delta^{-2} \Bigl[ \log (t) + \log \log(n) + \log(1/\delta) \Bigr] ~\in~ o(n / \log(n)) .$$ (We can neglect all of the contributions of $t$ to this.) From the above, we clearly have $\delta^{-2} \in o(n / \log^2(n))$, so we may consider $1/\delta \in o(\sqrt{n} / \log(n))$; this gives us $$O(N \log(N)) ~\subseteq~ o\left( n \log(n) / \log^2(n) \cdot \Bigl[ \log(n) - \log \log(n) \Bigr] \right) ~=~ o(n).$$ This is a sufficient condition. Then, with probability of failure $p \sim 1/n^t$, we can obtain a list $L$ which contains all of $M$, and any number of extraneous elements which scales faster than $\log(n)/\sqrt{n} \cdot n = \sqrt{n} \log(n)$. It's not hard to show that if we want $t = 0$ (that is, $1/p$ is constant), we get a modest improvement so that we require a number of extraneous elements scaling faster than $\sqrt{n \log(n)}$. If we choose for $1/\delta$ to grow substantially faster than $\Omega(\sqrt n)$, for instance $\delta \sim n^{-2/3}$, we can even achieve probabilities of failure which shrink exponentially quickly, as a trade-off for an increasing number of comparisons (but which is still asymptotically just larger than $n$).

You can also easily modify the algorithm to obtain a list which with high probability contains only elements among the highest $\sigma n$ elements of $V$, while omitting only $\delta n$ of them, or to identify in the list $L$ constructed above an element which with high probability is one of the $\sigma n$ elements of $V$; the analysis is similar in either case. If you want a more sophisticated result than this, which might achieve $n - o(n)$ comparisons (or even $n - O(n)$ comparisons), you will have to specify precisely what sort of error conditions are acceptable.

-