I realize that we must do a minimum of $n - 1$ comparisons to find the median in a list of numbers, therefore the time complexity would be $\Omega(n)$. However, given a hypothetical scenario in a world where the median can be found in $\mathcal O(log(n))$ time, what would be the implications on the fastest sorting time? Would this allow us to beat $\mathcal O(n\log(n))$ and sort in $\Theta(n)$ time?

  • $\begingroup$ @Evil yes sorry, I am confusing my self because I am having a hard time wrapping my head around the concept of finding the median in O(log(n) time. I have edited the question. $\endgroup$ – delhics Feb 6 '18 at 2:52
  • $\begingroup$ I have changed a bit your notation. If you talk about comparison based model and would like to count only comparisons, it may happen that it will be lower than $n$, given some insight. I am not sure if you are interested only in comparison based model and discard other methods (like counting sort or radix sort)? If you use your median you have cutted the problem in half, you can continue cutting, like using Quicksort with always perfect guess. Does it help? How many subarrays are there when you continue splitting by median? $\endgroup$ – Evil Feb 6 '18 at 21:22
  • $\begingroup$ Why would it change the complexity of sorting? The well-known lower bound on comparison sorts still applies. If you're thinking of quicksort, note that even if you found the median in logarithmic time, you'd still have to partition, which takes linear time. $\endgroup$ – Raphael Feb 6 '18 at 21:33

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.