5
$\begingroup$

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{equation} \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} \end{equation}

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{equation} \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} \end{equation}

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

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thank you so much for the insightful answer. I updated my question with more details. $\endgroup$ – zcadqe Aug 13 '18 at 2:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.