Probabilistic Analysis of the Randomized QuickSort Algorithm

8 min readJun 19, 2021

This article will cover the probabilistic analysis of the randomized Quicksort algorithm. The randomness comes from selecting the pivot to partition the input array around uniformly.

Overview / Pseudocode

Quicksort is an efficient algorithm that solves the sorting problem; that is, given an input array A and its length n, find a permutation of A such that for all i, j (0 ≤ i < j < n), A[i] < A[j]. The running time of Quicksort is in the order of Θ(n log n). The algorithm sorts an array by selecting a pivot element, “partition”ing the input array A around that pivot, and recursively sorting the left and the right arrays, as described below:

The Quicksort algorithm is said to be random because it chooses its pivot element randomly, as stated in the ChoosePivot algorithm.

Analysis

The running time of Quicksort depends on how well a pivot is chosen. Suppose the ChoosePivot subroutine always chooses the pivot element to be A[l] (the letter “l” is used, not 1). What’s the running time of quicksort if the array is already sorted?

The input array is sorted, which means it is the worst possible input for the partition subroutine. Since, now, the 1st element is always selected to be the pivot, and the array is sorted, the array will be partitioned as:

Thus, the first call to Quicksort subroutine will be Quicksort(A, 0, n-1), the second call will be Quicksort(A, 1, n-1), third Quicksort(A, 2, n-1), and so on. We can get the following recurrence with these recursive calls:

Θ(n) is the running time of the partition subroutine, T(n)’s are the recursive calls. We can easily see that the solution for this recurrence is Θ(n²) since, for every element in the array, the work done is in the order of Θ(n).

Let’s now suppose that the ChoosePivot subroutine selects the pivot element to be the median. What will be the running time of Quicksort?

When the array is partitioned, since the pivot is the median, we will have to equal-sized subarrays (let's call them left and the right):

Since at every step of recursion the array size shrinks by the factor of 1/2, and subproblem size doubles (left and right), we will have a recurrence analogous to the recurrence of the Merge Sort algorithm:

It is easy to prove that the solution to this recurrence is Θ(n log n) by induction or by using the Master Theorem¹.

The point is that the running time of the Quicksort algorithm depends on how “well” the pivot is chosen. We saw that if the first element is always chosen as a pivot, the running time becomes Θ(n²), and if the median is always chosen as a pivot, it becomes Θ(n log n).

A Better Way

One idea that may give us better results is choosing the pivot randomly in every recursive call. This approach might give the median element as a pivot, which is the case we’re hoping for, or, it might also give the first element as a pivot, which we don’t want.

Our hope from randomization is to get a pivot that is “pretty good”.

“Pretty good” doesn’t mean that ChoosePivot should always select the median element. As a matter of fact, if the length of an array A is n, numbers in the range [n/4, 3n/3] (25–75 split) will give Θ(n log n) time (This can be proven via recursion tree, but the tree will be unbalanced). For instance, if we have an array {1, 2, 3, …, 100}, and if the index of the pivot element is, let’s say, 36, the array will be divided into 2 subarrays, and 1st subarray’s length will be 35, 2nd subarray’s length will be 64. The idea is that this split (35–64) will be close to selecting the median element in terms of the running time.

Lemma 1

The probability that a randomly chosen pivot will give a 25–75 split or better in the input array A is 1/2.

Proof

The sample space Ω will be {1, 2, 3, …, n} (possible indices of the pivot element). The event of choosing a pivot that gives a 25–27 split or better is:

To complete the proof, we need to find the probability of the event S:

The proof is complete.

Theorem

For every input array of length n, the average running time of Quicksort with random pivots is O(n log n).

This theorem states that for every possible array, whilst the running time of quicksort fluctuates between O(n log n) and O(n²), the best case (n log n) dominates.

Proof

Part 1

Variables:

Array a with length n,

Sample space Ω: all possible random pivot indices = {1, 2, 3, … n}

We will define a random variable C:

Our goal is going to prove that 𝔼[C] = O(n log n).

To restate, we cannot apply the Master Theorem to calculate the running time since the pivot can give unbalanced splits.

Notation:

How many times can 2 fixed elements of A be compared during the execution of Quicksort?

The answer is 0 or 1. During partitioning, the pivot is compared with every element in the array exactly once. This indicates that if 2 elements are compared, then one of them must be a pivot. And if one element is chosen as a pivot, it would be excluded from the recursive calls; thus, it won’t be compared anymore. In essence, either 2 elements are compared if one of them is selected as a pivot in any recursive call, or they are not compared.

This makes the random variable X an indicator random variable, which means that its value is only 0 or 1. Any two elements can get compared only once or zero. So, the value of X becomes:

Recall that C(σ) is a random variable that holds the number of comparisons between all elements if the σth element is selected as a pivot. We can cleverly write C in terms of Xs:

Our goal is to compute the expectation of C, 𝔼[C], and it is:

Following from the linearity and definition of expectation,

We will have 𝔼[C] = Σ Σ p(X_ij = 1).

Part 2

To find 𝔼[C], we need to find the value of p(X_ij = 1).

Fix zi, zj (i < j). Consider the set S = {zi, zi+1, zi+2, …, zj-1, zj}. Recall that zi is the ith smallest element of A. As long as none of the elements of S is chosen as a pivot, elements of S are passed into the same recursive call. This is because if pivot < zi, set S will be on the right of the pivot and will get passed into the second recursive call, if pivot > zj, set S will be on the left of the pivot and will get passed into the second recursive call.

Consider the first element of S that gets chosen as a pivot:

Case 1: If zi or zj gets chosen pivot first among S, they are compared.
Case 2: If one of {zi+1, zi+2, …, zj-1} gets chosen first, then zi and zj are never compared (Because they will get passed into different recursive calls).

Each element of zi, …, zj is equally likely going to be the first to get selected as a pivot.

We are looking for p(X_ij = 1), which is the probability that zi and zj get compared. This is the probability of case 1. Since case 1 is an event, its probability is defined as:

the event Case 1 contains two elements, {zi, zj}; so, we’ll have:

Part 3 — Final Calculations

We are now at the stage of:

If we fix “i” to any value, the inner sum will become:

To make our lives easier, we will bound this summation to the summation on the left. (This means that, lets say a = ∑1/k, and b = ∑ 1/(j-i+1). a will always be greater than or equal to b if i is an integer that is greater than 0 (a = b if i = 1). Since i cannot be 0 (recall that zi is the ith smallest element of A), it is evident that a will always be greater than or equal to b. Here’s a link to verify this. ).

So: