Suppose we have a O(n) time algorithm that finds median of an unsorted array.…
2006
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.
- A.
O(n2 Logn)
- B.
O(n2)
- C.
O(n Logn Logn)
- D.
O(nLogn)
Attempted by 286 students.
Show answer & explanation
Correct answer: D
Key idea: At every recursive call we spend linear time to find the median and to partition, then recursively sort two halves of equal size.
Find the median of the current array in O(n) time using the given linear-time selection algorithm.
Partition the array around that median in O(n) time, producing two subarrays of size at most n/2 each.
Recursively apply the same process to each half.
Recurrence: T(n) = 2 T(n/2) + O(n), because each level does O(n) work (median selection + partition) and there are two recursive calls on size n/2.
Solve the recurrence: a = 2, b = 2 so n^{log_b a} = n. Since f(n) = Theta(n), by the Master Theorem the solution is T(n) = Theta(n log n).
Answer: O(n log n).
Intuition: Each recursion level costs O(n) in total because work per subproblem scales with its size, and summing sizes over all subproblems at a level yields n.
There are O(log n) levels because the problem size halves each recursion, so total is O(n) times O(log n) = O(n log n).