# Probability bounds on size of smaller partition in randomized quicksort

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.

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

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.
• 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. – Yuval Filmus Feb 13 '16 at 21:29