In quick-sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
A. Theta(n)
B. Theta(n log n)
C. Theta(n^2)
D. Theta(n^2 log n)
GATE 2009 · Algorithms · Quick Sort · medium
Answer: Worst-case time complexity is Theta(n log n). Answer: B.
Determine the partition sizes: The (n/4)th smallest element divides the array into: left subarray with n/4 - 1 (approximately n/4) elements smaller than the pivot, and right subarray with 3n/4 elements larger than the pivot. So every partition creates subarrays of size n/4 and 3n/4.
Write and analyze the recurrence: T(n) = T(n/4) + T(3n/4) + O(n). Using the recursion tree: at level 0, work = n. At level 1, two subproblems of sizes n/4 and 3n/4, total work = n/4 + 3n/4 = n. At every level, total work = n. The tree depth is determined by the larger subproblem: 3n/4 shrinks to 1 in log_{4/3}(n) levels. So total levels = log_{4/3}(n) = O(log n). Total work = n * O(log n) = Theta(n log n).
Confirm this is the worst case: Since the pivot selection algorithm always finds exactly the (n/4)th smallest element, the partition is always exactly n/4 vs 3n/4. This is deterministic — there is no 'better' or 'worse' input; every input gives the same partition behavior. Therefore, both best and worst case are Theta(n log n).