Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, let $d(i)$ be the number of elements that $S_{(i)}$ is compared to. Finally, the pivot element is chosen uniformly at random.
How do I then compute the probability that $d(i) < k$ for some $k \in \mathbb{N}$?
This is not the answer to your question, but maybe you can use some elements of it.
For $i<j$, let us denote $X_{ij}$ the random variable: $$X_{ij} = \left\{\begin{array}{rl}1 & \text{if }S_{(i)}\text{ and }S_{(j)}\text{ are compared}\\0&\text{otherwise}\end{array}\right.$$ and $A_{ij} = \{S_{(i)}, S_{(i+1)}, …, S_{(j)}\}$.
Since a comparison between two elements only occurs if one of them is a pivot, and since a pivot is never compared to other elements after the end of the partition occurring when it was chosen, we can conclude that:
$$\mathbb{P}(X_{ij} = 1) = \mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) + \mathbb{P}(S_{(j)} \text{ first pivot in }A_{ij})$$ This is also due to the fact that if another element of $A_{ij}$ is chosen as first pivot, $S_{(i)}$ and $S_{(j)}$ will be put in two different parts of the partition.
Since the choice of the pivot is uniform, we get $\mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) = \frac{1}{|A_{ij}|}$ and finaly $\mathbb{P}(X_{ij} = 1) = \frac{2}{j - i +1}$.
Now, the expected number of comparisons where $S_{(i)}$ is involved is:
$$\begin{array}{rcl} \displaystyle\mathbb{E}\left(\sum\limits_{j=1,j\neq i}^nX_{ij}\right) & = & \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{E}(X_{ij})\\ & = & \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{P}(X_{ij} = 1)\\ & = & \displaystyle\sum\limits_{j=1,j\neq i}^n\frac{2}{|j-i| + 1}\\ & = & \displaystyle\sum\limits_{j=1}^{i-1}\frac{2}{i - j +1} + \sum\limits_{j=i+1}^{n}\frac{2}{j - i +1}\\ & = & \displaystyle\sum\limits_{k=1}^{i-1}\frac{2}{k +1} + \sum\limits_{k=1}^{n-i}\frac{2}{k +1}\\ \end{array}$$
This analysis is generally sufficient for the analysis of the average time complexity of quicksort, because this value is $O(\log n)$. However, I am not sure as to how use part of it to find the value you want, which is: $$\displaystyle\mathbb{P}\left(\sum\limits_{j = 1, j\neq i}^n X_{ij} = k\right)$$
Also it is not so clear that for $j\neq j'$, $X_{ij}$ and $X_{ij'}$ are independant (since for example $X_{ij}$, $X_{ij'}$ and $X_{jj'}$ are not independant because at most two of the three could be $1$).
We can describe quicksort with a random pivot as follows. Assume for simplicity that $S_{(i)} = i$. First, choose a permutation of $\{1,\ldots,n\}$. Then, whenever processing some subarray, choose the element that appears first in the permutation as the pivot.
Suppose we are interested in the number of elements compared to $i$. Suppose that $i$ is found at location $j$. Suppose that when $i$ is chosen as a pivot, it is compared to $k_-$ elements smaller than itself and $k_+$ elements larger than itself. These elements must be $i-k_-,\ldots,i-k_+$, and the elements $i-k_--1,i+k_++1$, if they are in range, must appear before $i$. Let $b_-,b_+$ be the indicators of these elements being in range (i.e., $b_- = 1$ if $k_- < i-1$, and $b_+ = 1$ if $k_+ < n-i$).
Suppose that $j_-$ of the elements preceding $i$ are smaller than $i$, forming a set $S_-$, and so $j_+ = j - 1 - j_-$ of the elements preceding $i$ are larger than $i$, forming a set $S_+$. There are $\binom{i-1-k_--b_-}{j_--b_-}$ choices for $S_-$ and $\binom{n-i-k_+-b_+}{j_+-b_+}$ choices for $S_+$. There are $\binom{j_++j_-}{j_+}$ ways of putting them together, and $(n-j)!$ ways to choose the order of the remaining elements.
The number of permutations of $S_-$ with $\ell_-$ left-to-right maxima is the Stirling number of the first kind $\genfrac{\lbrack}{\rbrack}01{j_-}{\ell_-}$. Similarly, the number of permutations of $S_+$ with $\ell_+$ left-to-right minima is $\genfrac{\lbrack}{\rbrack}01{j_+}{\ell_+}$.
We obtain the following formula for the probability that $i$ is compared to exactly $s$ elements: $$ \frac{1}{n!} \sum_{j_++j_- \leq n-1} \sum_{\substack{k_++k_-+\ell_++\ell_-=s \\ k_- \leq i-1 \\ k_+ \leq n-i}} \\ \binom{j_++j_-}{j_+} \binom{i-1-k_--b_-}{j_--b_-} \binom{n-i-k_+-b_+}{j_+-b_+} \\ (n-j_+-j_--1)! \genfrac{\lbrack}{\rbrack}00{j_-}{\ell_-} \genfrac{\lbrack}{\rbrack}00{j_+}{\ell_+}. $$
