You have an array of \(n\) elements. Suppose you implement quicksort by always…
2014
You have an array of \(n\) elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
- A.
\(O (n^2)\) - B.
\(O(n \log n)\) - C.
\(\theta (n \ log \ n)\) - D.
\(O (n^3)\)
Attempted by 430 students.
Show answer & explanation
Correct answer: A
Answer: The tightest upper bound for the worst-case running time is O(n^2).
Reasoning:
Pivot selection: the algorithm always selects the element at the central index of the current subarray.
Worst-case input construction: arrange elements so that the chosen central-position element is the smallest (or the largest) of the subarray at every recursive step. Then partitioning places that pivot at one end, producing subproblems of sizes 0 and n-1 each time.
Recurrence and solution: with partitioning taking Theta(n) time at each level and one side of size n-1 to recurse on, the recurrence is T(n) = T(n-1) + Theta(n). This solves to T(n) = Theta(n^2), so the worst-case running time is O(n^2).
Clarification: although the average-case running time of quicksort (with random pivots or typical distributions) is Theta(n log n), that does not apply to the worst-case behavior when the pivot choice consistently produces highly unbalanced partitions.
A video solution is available for this question — log in and enroll to watch it.