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

  • $\begingroup$ "the smallest section is smaller than an", can you explain that? $\endgroup$
    – 3SAT
    Commented Feb 13, 2016 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$ Commented Feb 13, 2016 at 18:53
  • $\begingroup$ @JohnatanMorian Thanks -- that makes more sense. Close vote retracted. $\endgroup$ Commented Feb 13, 2016 at 21:50
  • $\begingroup$ What's your question? I don't see a question in this post. $\endgroup$
    – D.W.
    Commented Feb 15, 2016 at 7:17

1 Answer 1


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.

  • $\begingroup$ No, now it's time for you to think hard until you solve this. $\endgroup$ Commented Feb 13, 2016 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$ Commented Feb 13, 2016 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$ Commented Feb 13, 2016 at 21:35
  • $\begingroup$ No, I'm afraid you'll have to sweat it. $\endgroup$ Commented Feb 14, 2016 at 12:22
  • 1
    $\begingroup$ No. Please consult a local TA. Stackexchange cannot function as a private tutor. $\endgroup$ Commented Feb 14, 2016 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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