Question

Give an example input (6 elements) for quick sort which would result in worst case performance, (using the scheme of choosing the left-most element as the pivot).

Answer 1

The worst-case performance of quicksort can be achieved by a number of permutations of the input sequence. One such input sequence is when all the elements in the input sequence are of same value i.e say for our case it is [6, 6, 6, 6, 6, 6] or any other number with same value. This always gives the worst-case no matter what is the pivot because it has to go through all the elements and every step will produce a worst-case partitioning of the problem. Hence, the time complexity of quicksort with n elements having equal values is always O(n²).