0
$\begingroup$

Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with.

Let $A = A[1], ..., A[n]$ be an array of $n \ge 4$ distinct keys.

Describe an efficient algorithm to find the three smallest keys in $A$. Use words.

What is the worst case number of comparisons performed by your algorithm? Try to find an exact number. Ignore floors and ceilings. Explain your answer.

I would assume you use the randomized $k$-selection algorithm where $k=3$, but if you're recursively partitioning a group of integers around a pivot I'm not sure how you'd find $k=2$ and $k=1$ short of running the algorithm 3 times.

Ideas?

$\endgroup$
-1
$\begingroup$

Well, here's what I came up with.

You could use Merge Sort, which has a worse-case time complexity of $O(n (log (n))$, then take the first 3 values of the array, but it felt like this question was seeking the use of the Randomized Select algorithm.

Best case for Randomized Select would be select $3$ (or $1$) as your random pivot and then make a comparison to the left or right of that for the other two spots, giving you a complexity of $n-1+1$ or $\Omega(n)$.

But this is asking for worst case. By my calculation if an adversary is always picking the furthest pivot from the target (say $k=3$), then the time complexity would be: $$\frac{n(n-1)}{2} $$ For example. Let's say you have an unsorted array of $7,5,9,8$. The third smallest number is $8$ so the worst pivot is $5$. Compare $7,8,9$ (which is $n-1$ comparisons), you see there are 3 numbers greater.

The next worst pivot is either $7$ or $9$, so pick one of those, and $n-2$ comparisons, you see $8$ and $9$ are greater than 7. You know that $5$ is the smallest, $7$ is the second smallest, but you still need the third smallest. Repeat.

Pick $9$ as your pivot and make $n-3$ comparisons to see that $9$ is the 4th smallest, meaning $8$ is your 3rd smallest.

Add up those comparisons and simplify, you get the formula quoted above. Worst-case this seems less efficient than Merge Sort and selecting the first three numbers, but this seemed like the application of Randomized Select that the question was leaning toward (based on the book and classroom work).

Hope this helps someone else.

$\endgroup$
  • $\begingroup$ You can find the $k$ smallest elements in $O(n)$, for any constant $k$. You can use a heap of size $k$ or the deterministic linear time selection algorithm, for example. $\endgroup$ – Yuval Filmus Oct 4 '15 at 4:18
  • $\begingroup$ cs.stackexchange.com/questions/47715/… here's the $k=2$ case which you can use as the idea for $k=3$. $\endgroup$ – wvxvw Oct 4 '15 at 9:22
  • $\begingroup$ @xvxvw that's just a generic divide and conquer approach. $\endgroup$ – OrdinaryHuman Oct 4 '15 at 20:28
  • $\begingroup$ @YuvalFilmus yes, the running time of randomized select is $O(n)$, but that doesn't apply to the 2nd and 3rd elements. Not sure why both my question and attempt to answer it were downvoted -- one, it's not even my question, so I'm not sure how it cannot be clear. And two, how can an attempt to answer it not be clear? Am I not understanding how cs.stackexchange.com works? $\endgroup$ – OrdinaryHuman Oct 4 '15 at 20:30
  • $\begingroup$ @OrdinaryHuman Your running times are sub optimal. $\endgroup$ – Yuval Filmus Oct 5 '15 at 4:02

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.