What is the worst-case time complexity of the QuickSort algorithm?
Nopal Securities technical mcq question, verified with a worked answer. Free to practise - no sign-up.
What is the worst-case time complexity of the QuickSort algorithm?
Show answer & explanation
Answer: D. O(n^2)
When the chosen pivot is repeatedly the smallest or largest element (such as an already sorted array with first element as pivot), QuickSort degrades to O(n^2).
Step-by-step Derivation:
Step 1: The partitioning recurrence in the worst case produces subarrays of size 0 and n-1: T(n) = T(n-1) + O(n).
Step 2: Unrolling gives sum of 1 to n = n(n-1)/2 = O(n^2).