I was thinking maybe I can make it 2T(n/2) + C split the list into two halves and work on them recursively to partition the list.

  • 1
    $\begingroup$ Does your question asks whether it is possible to find median in logarithmic time (to split into two halves)? The answer is no, it is not possible to find median faster than linear time in unsorted array under general assumptions. $\endgroup$ – Evil Mar 14 '19 at 22:03
  • $\begingroup$ $T(n) = 2T(n/2) + C$ gives $T(n) = \Theta (n) $ $\endgroup$ – Peter Taylor Mar 15 '19 at 7:12

No. The partition operation must access every item in the list: if there is any item it does not look at, then you don't know which side of the partition it belongs on. Consequently, the partition operation cannot run any faster than $O(n)$ time, where $n$ is the length of the list.


No, this doesn't work. Whatever method it uses, your partitioning still has to look at every element of the list, even if that's hidden inside recursions.

Mathematically, you're confusing the recurrence $T(n)=2T(n/2)+c$ with the binary search recurrence $T'(n)=T'(n/2)+c$. $T'=\Theta(\log n)$ but $T(n)=\Theta(n)$. In binary search, you only have to recurse on one half; having to visit both halves kills you.

In fact, it's probably even worse. Saying that your partitioning scheme runs in time $T(n)=2T(n/2)+c$ is saying that you can combine the partitions of the two halves in constant time. The only way I can think of doing that would be using some kind of linked list data structure. But then splitting the list requires finding the middle, which is still $\Theta(n)$. Maybe you could do something with binary trees but, man, this is getting complicated and your best possible outcome is a complicated way of getting the $\Theta(n)$ partitioning time we already had with the simple algorithm on an array.


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.