# Randomised Median [closed]

I have tried hard , but i'm unable to come up with the expected running time for the number of comparisons to find the Randomized Median (find the median of an unsorted array). Also i wanted to make sure that we CANNOT take expectation of the recurrence that we use to find the randomized mean , or any other recurrence in any other problem as they belong to different probability spaces? Is this statement right?

• Have you been shown a way of calculating the expected running time of randomized quicksort? – Yuval Filmus Jan 29 '14 at 14:11
• What is the algorithm your question relates to? Talking about runtime without a concrete algorithm does not make much sense, and particularities may matter. What is the recurrence you have at hand? – Raphael Jan 29 '14 at 17:00
• @Raphael sry for that. I basically take a random pivot and divide the array . If the pivot is at position n/2 i return if less , I select the right par and recursively find element of rank -(n/2-rank(pivot)) if greater i recurse on right and find recursively element of rank n/2 – Aditya Nambiar Jan 29 '14 at 19:39
• @Yuval Yes we have been – Aditya Nambiar Jan 29 '14 at 19:40
• @Aditya In that case, try to mimic the argument you've seen. – Yuval Filmus Jan 29 '14 at 19:42

One approach would be to form up a recurrence for the expected running time $T(n)$. At each stage there is $O(n)$ processing, and the result is a new list of length distributed according to some distribution $D_n$ (for you to determine), and so we can write $$T(n) = O(n) + \operatorname*{\mathbb{E}}_{m \sim D_n} T(m).$$ This looks much less frightening when you substitute the actual distribution $D_n$ and replace the expectation with a (weighted) sum. Then it remains to solve the recurrence.
• If you partition with respect to the $k$th ranked pivot, then what you get on the left is a uniformly random permutation of the smallest $k-1$ elements, and what you get on the right is a uniformly random permutation of the largest $n-k$ elements. This is because the elements are put in the partitions in the order they are encountered in the array. So I don't see any problem with taking the expectation over the recurrence relation. – Yuval Filmus Jan 29 '14 at 19:46
• It's only different if you are dogmatic about the contents of your array. For me, $T(n)$ is the expected running time on any array consisting of distinct elements, ordered uniformly at random. – Yuval Filmus Jan 29 '14 at 19:52