2
$\begingroup$

Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-2a$ the smallest section be greater than $an$. How we can Calculate this probability? after 72 hours try i reach to following that means valid area is (1-a)n-an=n(1-2a). by dividing n(1-2a)/ n we get 1-2a. enter image description here

$\endgroup$
  • $\begingroup$ "the smallest section is smaller than an", can you explain that? $\endgroup$ – 3SAT Feb 13 '16 at 17:54
  • $\begingroup$ @Nehorai The smaller section of the array after pivoting (either the things less than the pivot or things greater than it) contains at most $an$ elements. $\endgroup$ – David Richerby Feb 13 '16 at 18:53
  • $\begingroup$ @JohnatanMorian Thanks -- that makes more sense. Close vote retracted. $\endgroup$ – David Richerby Feb 13 '16 at 21:50
  • $\begingroup$ What's your question? I don't see a question in this post. $\endgroup$ – D.W. Feb 15 '16 at 7:17
1
$\begingroup$

Suppose for simplicity that all elements are distinct, and that after sorting, these elements are $x_1,\ldots,x_n$. A random pivot has the same distribution as $x_i$ for $i$ chosen uniformly at random from $\{1,\ldots,n\}$. The size of the smaller partition is $\min(i-1,n-i)$. If $I$ is the set of indices $i$ such that $\min(i-1,n-i) \geq an$, then the probability you are looking for is $|I|/n$ (by the definition of uniform probability). I'll let you complete the calculation.

$\endgroup$
  • $\begingroup$ No, now it's time for you to think hard until you solve this. $\endgroup$ – Yuval Filmus Feb 13 '16 at 21:25
  • $\begingroup$ Make sure that you understand what probability means. The probability that the random index $i$ lies in some set $I \subseteq \{1,\ldots,n\}$ is $|I|/n$. In your case $I$ is the set of indices for which the smaller partition is larger than $an$. So you just have to calculate the size of $I$. If you don't solve such problems yourself you'll never get better. $\endgroup$ – Yuval Filmus Feb 13 '16 at 21:29
  • $\begingroup$ Perhaps you should take this opportunity to learn some basic probability. You can't expect to answer probability questions without knowing basic probability theory. This will only get worse as the course proceeds. $\endgroup$ – Yuval Filmus Feb 13 '16 at 21:35
  • $\begingroup$ No, I'm afraid you'll have to sweat it. $\endgroup$ – Yuval Filmus Feb 14 '16 at 12:22
  • 1
    $\begingroup$ No. Please consult a local TA. Stackexchange cannot function as a private tutor. $\endgroup$ – Yuval Filmus Feb 14 '16 at 18:27

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.