Understanding the upper bound proof for quick sort

Question

I'm trying to understand the average run time of quicksort which is $O(n \log n)$.

I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we essentially partition $\log n$ times and each partition performs $n$ comparisons. And this happens with high probability; e.g. partition to $c$ and $n-c$ for a constant $c$ is less likely because $c/n$ is smaller than $\alpha n/n$ for large $n$.

Now I want to prove this bound. The first observation is that if we consider a sorted array $A'$, then elements $A'[i]$ and $A'[j]$ are compared at most once. This is because we only compare with pivot and then remove it during partitioning. Therefore the expected number of comparisons becomes

\begin{align} \mathbb{E}\left[\sum_{i=1}^n \sum_{j=i+1}^n 1\{A'[i] \text{ compared with } A'[j]\} \right] = \sum_{i=1}^n \sum_{j=i+1}^n P\{A'[i] \text{ compared with } A'[j]\} \end{align}

It remains to compute the probability of comparing $A'[i]$ and $A'[j]$. Now one argument is that if we pick a pivot before $A'[i]$ or after $A'[j]$, then $A'[i]$ and $A'[j]$ remain together in the next subarray. So this probability becomes the probability of choosing $A'[i]$ or $A'[j]$ as a pivot in subarray $A'[i,...,j]$ which is simply $2/(j-i+1)$. My question is: Why do we only need to compute the probability of choosing $A'[i]$ or $A'[j]$ as a pivot only in subarray $A'[i,...,j]$?

I'm confused because I think at the beginning we have an array of length $n$ so there is a $2/n$ chance for picking them as a pivot, some chance $x_1$ to pick a pivot between them (so they'll never be compared), and some chance $1-x_1-2/n$ to pick a pivot before or after them (so they remain in the same subarray and may be computed). In the last case, again the probability of picking one $A'[i]$ and $A'[j]$ depends on the array length. How can I show that this line of thinking also gives the same runtime?

At the same time, it makes intuitive sense that the probability of comparison depends only on the number of elements between $A'[i]$ and $A'[j]$.

Answer 1

You have misunderstood the analysis of randomized quicksort.

The idea is that we can view pivot selection in randomized quicksort in the following way. We first select a permutation $\pi$ on the elements on the array. When choosing a pivot among some subarray $B$, we choose the element of $B$ which appears first in $\pi$.

Suppose that $i < j$. We are interested in knowing whether two elements $A'[i]$ and $A'[j]$ will ever be compared. In order for them to be compared, $A'[i]$ or $A'[j]$ needs to be chosen as pivot for some subarray which contains both of them. The elements $A'[i]$ and $A'[j]$ remain in the same subarray as long as none of $A'[i+1],\ldots,A'[j-1]$ is chosen as pivot. Hence $A'[i]$ and $A'[j]$ will be compared if in the permutation $\pi$, the first element among $A'[i],\ldots,A'[j]$ is either $A'[i]$ or $A'[j]$. This happens with probability $2/(j-i+1)$. We conclude that the expected number of comparisons is $$ \sum_{1 \leq i < j \leq n} \frac{2}{j-i+1} = \Theta(n\log n). $$ This expression represents the expected number of comparisons, not an upper bound on the number of comparisons. In the worst case, all elements will be compared to one another. The best upper bound on the number of comparisons is $\binom{n}{2}$.

---

Another way to estimate the expected number of comparisons is using your intuition. Denoting the expected number of comparisons by $T(n)$, we have $$ T(n) = n-1 + \frac{1}{n} \sum_{m=0}^{n-1} (T(m) + T(n-1-m)) = n-1 + \frac{2}{n} \sum_{m=0}^{n-1} T(m). $$ We also have $$ T(n+1) = n + \frac{2}{n+1} \sum_{m=0}^n T(m). $$ Subtracting, we get $$ (n+1) T(n+1) - n T(n) = 2n + 2T(n), $$ and so $$ \frac{T(n+1)}{n+2} = \frac{T(n)}{n+1} + \frac{2n}{(n+1)(n+2)}. $$ It follows that $$ T(n) = (n+1) \sum_{m=1}^{n-1} \frac{2m}{(m+1)(m+2)} = \Theta(n \log n). $$