2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I don't understand how you complicated yourself like that. Isn't it true that for any constant $\alpha$ you choose, the probability of choosing a pivot that will yield one of the sets to be smaller than $\alpha\cdot n$ is at most $2\alpha$ since there are $2\alpha\cdot n$ such pivots. Each time this happens, it adds "another" need to find a new pivot, hence adds $O(n)$ to the running time. But the probability that this will happen more than $O(\log(n))$ times (hence making the running time bigger than $O(n\log(n))$) is extremely small (try to calculate it). Now, find the expected value. $\endgroup$
    – nir shahar
    Jun 19, 2021 at 22:57
  • $\begingroup$ I might be wrong, so please don't take this as granted. Take it as a room for thought :) $\endgroup$
    – nir shahar
    Jun 19, 2021 at 22:58
  • $\begingroup$ The title of your question name a problem not addressed in the body. $\endgroup$
    – greybeard
    Jun 20, 2021 at 4:20

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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