# Randomized Algorithm for determining items with rank $\geq n/16$

Problem: We say that an item $x$ is of rank $m$ if there are $m$ items in the set less than $x$. Design a randomized algorithm to find all of the items in a set of size $n$ with rank greater than $\frac{n}{16}$ with probability of failure $\frac{1}{1024}$.

I had this problem on my final yesterday and it completely stumped me. I don't even know how to begin. Any hints would be appreciated.

• Could you report the exact text of the exercise? As you've written it, there is a trivial deterministic linear-time algorithm (select the n/16-th element, partition around that). – quicksort Dec 23 '17 at 8:07