Quicksort worst-case and averages-case analysis

Quicksort algorithm was developed by a British computer scientist Tony Hoare in 1959.  Quick Sort is capable of sorting a list of data elements significantly faster (twice or thrice faster) than any of the common sorting algorithms and that’s why it is the favourite topic of interviewers in programming interviews. It is one of the most efficient sorting algorithms and is an in-place sorting algorithm. 

Quicksort(A, start, end) { 

	if (start < end) { 
		partitionIndex = partition(A, start, end); 
		Quicksort(A, start, partitionIndex-1); 
		Quicksort(A, partitionIndex+1, end); 
	} 

} 

Now partition procedure, rearranges the array such that pivot element is at its correct position. The total time taken to rearrange the array is always 𝑂(𝑛) where n = end-start+1.

partition (arr[], low, high) {

    // selecting pivot – Element at end position (right most)
    pivot = arr[high];
    i = (low - 1);

    for (j = low; j <= high-1; j++) {
        // If current element is smaller than the pivot, swap the element 
        // with pivot to the left
        if (arr[j] < pivot) {
            i++;    // increment index of smaller element
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);

    return (i + 1);
}

You could read more about Quicksort and its implementation here.

Let us suppose that the pivot has divided the array into two parts, one of size k and other of size n-k. Both of these parts will need to be sorted. This gives us the following relation

𝑇(𝑛) = 𝑇(𝑘) + 𝑇(𝑛−𝑘) + Θ(𝑛),

where T(n) is time taken by algorithm to sort n elements and Θ(n) is the cpu time to rearrange n elements. Now, let’s analyse, worst case and best case.

Worst Case

Consider the case when pivot is the least element of array, we have k = 1.

Rearranging the terms,

Substituting n = n – 1,

Solving recurrence by substitution:

Likewise,

Now, such a recurrence can only go upto i = n-1, because otherwise n-i would be less than 1. Therefore,

which is O(n^2) . This happens when the array is already sorted.

Best Case

The best case occurs when the pivot divides the array into two equal parts in every step. Thus we have, k = n/2.

Therefore the recurrence becomes,

Substituting n = n/2,

Using substitution:

Similarly, we can generalize

This will continue until n = 2^k i.e. until k = logn . Thus,

which is  O(n logn) .

Best case analysis using Master Theorem (Optional)

Let T(n) denote the time complexity of Quicksort. The recurrence relation for the best case of Quicksort is:

To solve the recurrence, we can use the Master Theorem:

where,

• a = 2 (number of subproblems)
• b = 2 (factor by which the problem size is reduced)
• d = 1 (since rearranging the array elements takes linear time ie. O(n))

Using the Master Theorem:

1) Calculating the value of \log_b(a) :

2) Compare d with \log_b(a) :

In this case, d = 1 and \log_2(2) = 1 . Since d = \log_b(a), the time complexity is:

This proves that time complexity of Quicksort in best case is O(n logn) .