# Quick sort algorithm average case complexity analysis

This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications".

The quick sort is an efﬁcient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm begins by taking the ﬁrst element $a_1$ and forming two sublists, the ﬁrst containing those elements that are less than $a_1$, in the order they arise, and the second containing those elements greater than $a_1$, in the order they arise. Then $a_1$ is put at the end of the ﬁrst sublist. This procedure is repeated recursively for each sublist, until all sublists contain one item. The ordered list of $n$ items is obtained by combining the sublists of one item in the order they occur.

In this exercise we find the average-case complexity of the quick sort algorithm, assuming a uniform distribution on the set of permutations.

a) Let X be the number of comparisons used by the quick sort algorithm to sort a list of n distinct integers. Show that the average number of comparisons used by the quick sort algorithm is $E(X)$ (where the sample space is the set of all $n!$ permutations of $n$ integers).

b) Let $I(j,k)$ denote the random variable that equals 1 if the $j^{th}$ smallest element and the $k^{th}$ smallest element of the initial list are ever compared as the quick sort algorithm sorts the list and equals 0 otherwise. Show that $X = \sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}$.

c) Show that $E(X) = \sum_{k=2}^{n} \sum_{j=1}^{k-1} p$, where $p$ is the probability that the $j^{th}$ smallest element and the $k^{th}$ smallest element are compared.

d) Show that $p$ (the $j^{th}$ smallest element and the $k^{th}$ smallest element are compared), where $k > j$, equals $2/(k − j + 1)$.

I didn't have any particular problem with parts a, b and c.

I think that I managed to understand parts a, b and c.

For part a, this seems obvious from the definition of expected value. E(X) is the average value of the number of comparisons, weighted by the probability that the permutation has a particular order (which is $1/n!$).

For part b, I verified that the sum $\sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}$ gives $I_{1,2} + I_{1,3} + I_{2,3} + I_{1,4} + I_{2,4} + I_{3,4}+\cdots+I_{n-1,n}$, that is, it gives the value of $I_{j,k}$ for every combination of $j$ and $k$. So, it sums 1 to every pair of integers that will be compared. Since the only situation two integers get compared is when one of them the the first element of the list (also called the "pivot"), this means that these two integers will go each one to separate sublists, so that they will not be compared anymore (in other words, every pair of integers is compared at most once). Therefore, it makes sense to say that the mentioned sum will give $X$, the total number of comparisons made by quick sort.

Part c also seems straightforward. The result follows from the linearity of the expected value (the expected value of a sum is the sum of the expected values): $E(X) = E\left(\sum_{k=2}^{n}\sum_{j=1}^{k-1}I_{j,k}\right) = \sum_{k=2}^{n}\sum_{j=1}^{k-1}E(I_{j,k})$. The value of $E(I_{j,k})$ (the expected value of $I_{j,k}$) is 1 times the probability that $I_{j,k}$ gets the value 1; the probability that $I_{j,k}$ gets the value 1 is the probability that the $j^{th}$ smallest element and the $k^{th}$ smallest element are compared, so $I_{j,k} = p$. So, $E(X) = \sum_{k=2}^{n}\sum_{j=1}^{k-1}p$.

Part d is where I got stuck.

I tried to reason the following way: given a list that will be ordered by quick sort, two integers $a_j$ and $a_k$ will get compared only if one of them is the pivot. Also, if a number that is smaller than $a_k$ and greater than $a_j$ is the pivot, $a_k$ and $a_j$ will go to separate sublists, so that they will never get compared. Otherwise, if the pivot is either greater than both $a_k$ and $a_j$, or smaller than them, $a_j$ and $a_k$ will both go to the same sublist, so that, in another recursive call of the algorithm, they may still get compared.

But I'm not sure how to show that the probability that the $j^{th}$ smallest element and the $k^{th}$ smallest element are ever compared is $2/(k − j + 1)$. Could anyone give a hint? I would prefer a hint over a complete solution, so that I can discuss it further in comments to fill in the holes.

-
Your second last paragraph is a good proof. There are 2 favorable cases and $k-j+1$ cases in total. The probability is the ratio of favorable cases to total cases. – Byron Schmuland Jun 29 '12 at 2:33
@ByronSchmuland: actually, I'm not sure why this works as a proof. There is some reason that allows me to consider that there are $k-j+1$ cases in total, but I don't really understand why. For example, it appears that, in the first recursive call of the algorithm, the probability that the pivot is either $a_j$ or $a_k$ would be $2/n$. – anonymous Jul 1 '12 at 18:26
You just need to consider the first time that the algorithm selects one of the $k-j+1$ values between the $k$th and $j$th largest. It doesn't matter on which call of the algorithm this occurs. Despite your doubts, your proof is perfectly valid! – Byron Schmuland Jul 3 '12 at 6:31
@ByronSchmuland, your comment was helpful. Now I understand that, at some call of the algorithm, one of the $k-j+1$ elements between the $k^{th}$ and $j^{th}$ largest is going to be chosen as the pivot, but it doesn't matter on which call this occurs. – anonymous Jul 15 '12 at 19:11

Consider the set $z_{i,j} = \{z_i,z_{i+1},....,z_{j-1},z_j\}$ This set order is in terms of the values (not the order in the Array) i.e. $z_i<z_j \;and\; j>i$. As long as none of the these are chosen as pivot,all are passed to the same recursive call.
i.e. pivot $\leftarrow$ x
$x > z_{j} or \; x<z_{i}$ , $z_{i,j}$ is passed to same recursive call.
Consider the case when either of $z_{i},...z_{j}$ gets chosen as pivot.
a) if $z_i$ or $z_j$ gets chosen first, then $z_i$ and $z_j$ get compared.
b) if one of the $z_{i+1} ... z_{j-1}$ gets chosen first,then $z_i$ and $z_j$ are never compared.
$Pr\{z_i z_j compared\} = Pr\{X=z_i\} + Pr\{X=z_j\}$

PS: $Pr\{X=z_i\} = Pr\{X=z_j\} = 1/(j-i+1)$

I hope it helps.

-
Thank you, this answer was very helpful. The point that it helped me understand is that I only need to consider the $j-i+1$ elements $z_i$ through $z_j$, because, at some recursive call of the algorithm, one of them is going to be chosen as the pivot. – anonymous Jul 15 '12 at 19:07