Project ForgeAlgorithms
Sorting & Searching
GATE 2009
Hard
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Θ(n)
- Θ(n log n)
- CΘ(n²)
- DΘ(n² log n)
Explanation
Since the pivot always splits the array into fixed fractions (n/4 and 3n/4) rather than an adversarial 0-and-(n-1) split, the recurrence T(n)=T(n/4)+T(3n/4)+O(n) applies in EVERY case (this is the only case, deterministic). Any split into two constant fractions of n yields Θ(n log n), regardless of the exact ratio.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.