Question

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

• A. $0\left(n^3\right)$
• B. 0(nlogn)
• C. $\Theta \left(nlogn\right)$
• D. $0\left(n^2\right)$

Answer 1

The correct option is D $0\left(n^2\right)$

Choosing the central element (middle) as the pivot always can not make the partition into equal parts.
$\therefore$ The worst case time complexity
= 0($n^2$)