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?

  • $\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.

| cite | improve this answer | |
  • $\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.