# Randomized quicksort expected running time analysis

I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis.

### Setting in CLRS

First let $Z = \{z_1, ..., z_n\}$ be the set of elements of the input array $A$ in sorted order. $X$ is defined as the number of comparison we make (i.e., between pivot and an element). Because any two elements of the array $A$ is compared at most once, we have $X = \sum_{i=1}^{n-1} \sum_{j = i+1}^{n} X_{ij}$ where $X_{ij} = 1$ if $z_i$ and $z_j$ are compared. So we just need to calculate the expectation, $\mathbb{E} \left[ X \right] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \mathbb{P} \left(X_{ij} = 1\right)$.

So we just need to calculate $\mathbb{P} \left(X_{ij} = 1\right)$. According to the book, $\mathbb{P} \left(X_{ij} = 2\right) = \frac{1}{j - i + 1}$ and I don't follow this result.

### My analysis

Let $k$ be the index of the randomly selected pivot. Conditioning on the event that $k \in Z_{ij}$ where $Z_{ij} = \{z_i, z_{i+1}, ..., z_j\}$,

\begin{aligned} \mathbb{P} \left(X_{ij} = 1\right) &= \mathbb{P} \left( \left.X_{ij} = 1 \right| k \in Z_{ij}\right) \mathbb{P} \left(k \in Z_{ij} \right) + \mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \mathbb{P} \left(k \not\in Z_{ij} \right) \\ &= \frac{2}{j - i + n} \frac{j - i + 1}{n} + \mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \left(1 - \frac{j - i + 1}{n} \right). \end{aligned}

From this, we can see that if $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) = \mathbb{P} \left(X_{ij} = 1 \right)$, then indeed $\mathbb{P} \left(X_{ij} = 1 \right) = \frac{2}{j-i+n}$ agreeing the book's result. But I don't think that equality holds.

Suppose we choose pivot $k > j$ which is not in $Z_{ij}$. Then, we reduce the problem size to $\{1, ..., k-1\}$. Because $z_i$ and $z_j$ still belong to the same partition, we are given another chance to pick another pivot such that it is either $i$ or $j$. So I would expect that $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) = \mathbb{P} \left(X_{ij} = 1 \right)$ does not hold.

### Question

Is my analysis correct, i.e., $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \not= \mathbb{P} \left(X_{ij} = 1 \right)$? If not, how to derive $\mathbb{P} \left(X_{ij} = 1 \right)$ considering the fact that if the chose pivot is not in $Z_{ij}$ we are given another chance?

### Update

Yuval Filmus' answer is very good and complete in itself. But let me just add a little more step just for completeness. In particular steps leading to $\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1}$ were not trivial to me. So hopefully this may help others.

As Yuval Filmus said we can prove that $p(n,i,j) = 2/(j-i+1)$ using (strong) induction (over $n$). First check the base case which is $n = 2$ because we need at least two elements in order to even think about comparing $z_i$ and $z_j$. With $n = 2$, $j = 2$, $i = 1$ and $p(2,1,2) = \frac{2}{2 - 1 + 1} = 1$. If we have 2 elements, then pivot has to be one of them, and $\mathbb{P} \left(X_{ij} =1; 2\right) = 1$. This proves the base case.

Now consider the inductive step. Assume that $p(m,i,j) = \frac{2}{j-i+1}$ for all $m < n$. In particular, note that all the values of the first argument of $p(\cdot, \cdot, \cdot)$ inside both summations are less than $n$. Hence, we can plug in $p(m,i,j) = \frac{2}{j-i+1}$.

\begin{aligned} p(n,i,j) &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{1}{n} \sum_{k=1}^{i-1} \frac{2}{(j-k)-(i-k)+1} + \frac{1}{n} \sum_{k=j+1}^{n} \frac{2}{j-i+1} \\ &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{2}{n} \frac{i-1}{j-i+1} + \frac{2}{n} \frac{n-j}{j-i+1}, \end{aligned}

which is the expression given by Yuval Filmus. The rest of the step is in his answer.

Let us denote by $p(n,i,j)$ the probability that $X_{ij} = 1$ given that there are $n$ elements.
Let $k$ be the first chosen pivot. If $k \in \{i,j\}$ then $X_{ij} = 1$. If $i < k < j$, then $X_{ij} = 0$. Otherwise, if $k < i$ then $X_{ij} = 1$ with probability $p(n-k, i-k, j-k)$, and if $k > j$ then $X_{ij} = 1$ with probability $p(k-1, i, j)$. Altogether, we get $$p(n,i,j) = \frac{2}{n} + \frac{1}{n} \sum_{k=1}^{i-1} p(n-k, i-k, j-k) + \frac{1}{n} \sum_{k=j+1}^n p(k-1,i,j).$$ We can now prove that $p(n,i,j) = 2/(j-i+1)$ by induction, by noticing that $$\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1} = \\ \frac{2}{n} + \frac{2}{n} \cdot \frac{n-(j-i+1)}{j-i+1} = \\ \frac{2}{n} + \frac{2}{j-i+1} - \frac{2}{n} = \\ \frac{2}{j-i+1}.$$ Another way to get this result is to follow the algorithm until the first time when a pivot (at any level of recursion) in $\{i,\ldots,j\}$ gets selected. Elements $i$ and $j$ are compared if and only if this pivot happens to be $i$ or $j$, which happens with probability $2/(j-i+1)$.