Analysis of QuickSort Expected Time Complexity: Without Counting the Number of Comparisons

Question

While reading CLRS (4th ed.) regarding the analysis of the expected time for QuickSort, I encountered an alternative approach. The analysis involves the following steps:

1. Given an array of size $n$, the probability of choosing any particular element as a pivot is $1/n$. To formalize this, an indicator random variable $X_i$ is introduced, defined as $X_i = I\{i\text{-th smallest element is chosen as the pivot}\}$. It is evident that the expected value of $X_i$, denoted as $\mathbb{E}[X_i]$, is equal to the probability of $X_i$ being $1$, which is $\frac{1}{n}$.

2. Let $T(n)$ be a random variable representing the running time of QuickSort on an array of size $n$. The expected running time, denoted as $\mathbb{E}[T(n)]$, is expressed as:

$$\mathbb{E}[T(n)] = \mathbb{E}\left[\sum_{q=1}^{n}{X_q (T(q-1) + T(n-q) + Θ(n))}\right]$$

This part is clear and understandable.

3. The goal is to demonstrate that: $$\mathbb{E}[T(n)] = Θ(n) + \frac{2}{n}\sum_{q=1}^{n-1}{\mathbb{E}[T(q)]}.$$

In proving part 3, encountering challenges arises. Attempting to use the linearity property of expectation faces an obstacle due to the presence of multiplication, as seen in $\mathbb{E}[X_q T(q-1)]$. Unlike independent variables, these cannot be expressed as the product of their individual expectations ($\mathbb{E}[X_q]\mathbb{E}[T(q-1)]$), since the choice of the pivot element affects the algorithm's running time.

To address this issue and prove the statement, a different strategy or method needs to be employed.

Answer 1

This exercise is indeed wrong as written, I don't think there is any reasonable probability space on which variables $T(k)$ for all $k$ can be defined in such a way that it works.

But the idea can be made to work. The Quicksort algorithm consists of 4 steps:

• Random choice of a pivot
• Partition
• Sorting the left part
• Sorting the right part

Let $T_n$ be the random variable representing the runtime of Quicksort on an array of length $n$ with distinct elements, and let $P_n$, $L_n$, $R_n$ be the runtimes for partition, left sort and right sort respectively. Let $A_i$ be the event "the $i$-th smallest element is chosen as a pivot". The main idea is that if the $i$-th element is chosen as a pivot, then the left sort works exactly as quicksort on $i-1$ elements, and the right sort - as quicksort on $n-i$ elements. This means that the conditional distribution $\mathbb{P}(L_n = t|A_i)$ coincides with the distribution $\mathbb{P}(T_{i - 1}=t)$, and the same for the right: $\mathbb{P}(R_n = t|A_i) = \mathbb{P}(T_{n-i}=t)$. In particular, the conditional expectations are $\mathbb{E}(L_n|A_i) = \mathbb{E}T_{i - 1}$, $\mathbb{E}(R_n|A_i) = \mathbb{E}T_{n - i}$. This means that $$\mathbb{E}(P_n + L_n + R_n|A_i) = \Theta(n) + \mathbb{E}T_{i - 1} + \mathbb{E}T_{n - i},$$ and from the total expectation law we obtain $$\mathbb{E}(T_n) = \mathbb{E}(P_n+L_n+R_n) = \sum_{i = 1}^n \mathbb{E}(P_n+L_n+R_n|A_i) \mathbb{P}(A_i) =$$$$= \Theta(n) + \frac1n\sum_{i=1}^n (\mathbb{E}T_{i - 1} + \mathbb{E}T_{n - i})$$

Answer 2

Let's start with the equation you wrote in part 2:

$\begin{aligned} E[T(n)] & =E\left[\sum_{q=1}^{n} X_q(T(q-1)+T(n-q)+\Theta(n))\right] \\ & =\sum_{q=1}^{n} E\left[X_q(T(q-1)+T(n-q)+\Theta(n))\right] \end{aligned}$

by linearity of the expectation. Now, since $X_q$ is independent from other random choices in the recursive calls (note that there are no functional dependencies between the choice of the pivot in one recursive call and in the next recursive calls: the pivot is always chosen in the same random way in each recursive call, without taking into account how a pivot has been chosen in previous recursive calls; moreover, the pivot is selected with the same probability in each recursive call, owing to the fact that the elements are assumed to be distinct):

$E[T(n)] =\sum_{q=1}^{n} E\left[X_q\right] \cdot E[T(q-1)+T(n-q)+\Theta(n)]$

and, reusing again linearity of expectation and the fact that $E[X_q] = 1/n$ (this is because we are assuming the $n$ elements are all distinct, so that the expectation is equal to the probability of $X_q$ of being equal to 1):

$E[T(n)] =\frac{1}{n} \sum_{q=1}^{n} E[T(q-1)]+\frac{1}{n} \sum_{q=1}^{n} E[T(n-q)]+\frac{1}{n} \sum_{q=1}^{n} \Theta(n)$

Now, note that the first two summations have identical terms, obtained varying $q$ form 1 to $n$, so that we can conclude

$E[T(n)] =\frac{2}{n} \sum_{q=1}^{n} E[T(q)]+\Theta(n)$

Starting from this equation it is possible to prove that

$E[T(n)] \leq c n \lg n$ for a positive constant $c > 0$.