Question

In quick sort, for sorting n elements , the (n/4)${}^{th}$ smallest element is selected as pivot using an 0( n) time algorithm. What is the worst case time complexity of the quick sort?

• A. $\Theta$(n log n)
• B. $\Theta$(n)
• C. $\Theta$(n${}^2$ log n)
• D. $\Theta$(n${}^2$)

Answer 1

The correct option is A $\Theta$(n log n)

The relation T(n) = T(n/4) + T(3n/4) + n The pivot element is selected in such a wasy that it will divide the array into 1/4th and 3/4th alwaays solving this relation give $\Theta$(n log n).