# Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

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}$$?

• The question in the title is different from the question in the body. Are you interested in counting how may comparisons involve $S_{(i)}$? How many pivots are compared to $S_{(i)}$? How many elements is $S_{(i)}$ compared to as a pivot? May 16, 2021 at 18:56

This is not the answer to your question, but maybe you can use some elements of it.

For $$i, 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_+}.$$