1
$\begingroup$

In a hypothetical world, we have a machine that can find median of $n$ numbers in $O(\sqrt{n})$. (Of course this machine is not real).

Can we use this machine to sort an array in $O(n)$?

I don't know how can I approach these type of questions which have a wrong statement as given. I know if the machine also partitions the array when finding the median, we can sort the array in $O(n)$ using $T(n) = 2T(n/2) + O(\sqrt{n})$.

But the question didn't say anything about partitioning. So if we assume that it doesn't change the array in any way and just finds the median, Can we use this machine to sort the array in $O(n)$ or not?

$\endgroup$
  • $\begingroup$ Easy. Finding the median is $\Theta(n)$, therefore sqrt(n) >= cn, and since we can sort in O(n^2 / sqrt(n)), we can sort in O(n). $\endgroup$ – gnasher729 Jan 20 at 18:51
  • 1
    $\begingroup$ "In a hypothetical world, we have a machine that ..." actually means that "We are given a hypothetical machine that ..., hence this world becomes a hypothetical world." That is, we can use whatever we can do besides using this machine. In particular, you can use the partition technique. $\endgroup$ – John L. Jan 20 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.