Probability bounds on size of smaller partition in randomized quicksort Let $0 &lt; a &lt; 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.
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.