Question

An implementation of quicksort has its best case of O(nlogn) on an array that is already sorted (smallest to largest). What case is an inverse sorted array (i.e. largest to smallest), and what will be the time complexity? Explain.

Answer 1

Worst-case analysis:

In inverse sorted array (largest to smallest) the quick-sort give the worst case because in this if the pivot selected is either the smallest or the largest number then the sublist returned by partitioning routine (partition function) is of size n-1.

If this happens recursively in every partition, then each recursive call processes a list of size one less than the previous list. Thus, we make n-1 nested calls before we reach a list of size 1. This means that the call tree is a linear chain of n-1 nested calls. The i^th call does O(n-i) work to do the partition, and thus the summation of the whole partitioning operation is .

Hence, in this case, the quicksort takes O(n²) time.

Even in an increasingly sorted array (smallest to largest), it gives the time complexity of O(n²), because here also the sublist returned by the partitioning routine (partition function) is of size n-1 if the pivot selected is smallest or largest number.

Best-case analysis:

The best-case occurs if each time we perform a partition we divide the list into two nearly equal pieces. So, each recursive call processes a list of half the size. Thus, we make only log₂ n nested calls before we reach a list of size 1. This means that the depth of the call tree is log₂ n and as a result, the algorithm uses only O(n log n) time.