The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot? A. Theta(n) B. O(n log n) C. Theta(n log n) D. Theta(n^2)

GATE 2006 · Algorithms · Quick Sort · easy

Answer: Quicksort with median as pivot runs in Theta(n log n) time. Answer: C.

1. Write the recurrence: With median as pivot: partition is perfectly balanced into two halves of size n/2 each. Finding the median costs O(n), and partitioning costs O(n). So T(n) = 2T(n/2) + O(n).
2. Apply Master Theorem: a=2, b=2, f(n)=Theta(n), n^(log_2 2) = n^1 = n = Theta(n). Since f(n) = Theta(n^(log_b a)), this is Master Theorem Case 2: T(n) = Theta(n log n).