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.
$\begingroup$
$\endgroup$
4
1 Answer
$\begingroup$
$\endgroup$
7
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.
answered Feb 13, 2016 at 21:20
-
$\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
an", can you explain that? $\endgroup$