1
$\begingroup$

So we have an unsorted array, we need to find the first $m$ elements in ascending order (or $m$ smallest elements) where $m = \mathrm{array.size}/2$ (or $n/2$). How would we do this in linear $O(n)$ time.

What I was thinking of doing was use the SELECT algorithm to find the kth smallest element until $k = m$, but this way the complexity would be $n/2 \cdot O(n) = O(n^2)$.

$\endgroup$
  • 2
    $\begingroup$ You want to find the $m$ smallest numbers, and they have to be sorted? If yes, it is not possible to do so because it will give a $O(n)$ solution to sort the entire array and this violates the fact that comparison-based algorithm must sort in $\Omega(\log n)$ $\endgroup$ – Christopher Boo Mar 12 at 5:22
  • $\begingroup$ @ChristopherBoo I think that “in ascending order” might explain what we mean by “first $m$ elements”. $\endgroup$ – Yuval Filmus Mar 12 at 9:15
2
$\begingroup$

Find the median in $O(n)$ time. Then go over the array and take out all elements smaller than the median.

$\endgroup$
1
$\begingroup$

You can create a min heap ($O(n)$) and then perform extract min m times. ($O(mlogn)$). Time complexity will be $O(n) + O(nlogn)$.

$\endgroup$
  • $\begingroup$ While this does not answer How would we [find the $m$ smallest elements] in linear $O(n)$ time, it does present how to find the first $m$ elements in ascending order. $\endgroup$ – greybeard Mar 12 at 9:26

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.