The QuickSelect$($A$,$ k$)$ algorithm for finding the kth smallest element in an unsorted array

A picks an arbitrary pivot, then partitions the array into three pieces: the elements less than

the pivot, the elements equal to the pivot, and the elements that are greater than the pivot.

It is then recursively called on the piece of the array that still contains the kth smallest

element.

$($a$)$ Consider the array A $=[1,2,...,$ n$]$ shuffled into some arbitrary order. What is the

worst$-$case runtime of QuickSelect$($A$,$ n$/2)$ in terms of n$?$ Construct a sequence of

$$bad$$ pivot choices that achieves this worst$-$case runtime.