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?


closed as unclear what you're asking by Raphael Jan 29 '14 at 17:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Have you been shown a way of calculating the expected running time of randomized quicksort? $\endgroup$ – Yuval Filmus Jan 29 '14 at 14:11
  • $\begingroup$ 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? $\endgroup$ – Raphael Jan 29 '14 at 17:00
  • $\begingroup$ @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 $\endgroup$ – Aditya Nambiar Jan 29 '14 at 19:39
  • $\begingroup$ @Yuval Yes we have been $\endgroup$ – Aditya Nambiar Jan 29 '14 at 19:40
  • $\begingroup$ @Aditya In that case, try to mimic the argument you've seen. $\endgroup$ – 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.

  • $\begingroup$ In quicksort it was pointed out that we could not take expectation over the recurrence relation since the probability space for T(n) is different from T(n-k) or T(k) {which were in the recurrence relation). Hence we did that indicator random variable and found probability 2/(j-i+1) and solved it. Doesnt the same apply here $\endgroup$ – Aditya Nambiar Jan 29 '14 at 19:43
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 29 '14 at 19:46
  • $\begingroup$ The indicator random variable trick is just a different way of tackling the problem. You can try to apply it here as well. If you're not successful, either try a little harder, or follow the other approach. $\endgroup$ – Yuval Filmus Jan 29 '14 at 19:47
  • $\begingroup$ Hence the probability space for the left part would be all permutation of k elements and probabilities of right part all permutation of n-k elements which is diff from earlier probability space. However expectation add only over same probability space. $\endgroup$ – Aditya Nambiar Jan 29 '14 at 19:48
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 29 '14 at 19:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.