Quick sort always chooses the last element as the pivot. Which input causes its worst-case O(n²) running time?
Correct answer A. An array that is already sorted
Explanation
With the last element as pivot, a sorted array makes every pivot the maximum, so each partition splits off zero elements on one side and n − 1 on the other. That gives n levels of linear work, O(n²). Random input yields balanced partitions on average and O(n log n). Shuffling or choosing a random pivot avoids this predictable worst case.
Answer checked How we write and check questions
Discussion