$(10$ points$)$ Given a set of $n$ numbers, we wish to obtain the i largest in sorted order, for $i$ a small constant. That

is$,$ i does not grow when $n$ grows. Consider the following algorithm: Use Select$(L,k)$ from the slide set to find

the $i^{th}$ largest value, partition the list around this value using Partition from QuickSort, and then sort the i values

in the left right set of the partition. Answer the following:

$($a$)$ Describe a worst case data set, and say why it is the worst. An example for a particular value of $n$ and i will

receive partial credit. For full credit, you need to describe the data set in terms of $n$ for a small arbitrary

constant $i,$ which you may not fix to be a specific value. For example, a worst case data set of size $n$ for

QuickSort is one that is already sorted.

$($b$)$ What is the worst case order complexity of the algorithm described; that is$,$ what is the order complexity

of the number of comparisons your algorithm performs on this worst case data set? Support your answer.

You do not need to write the full pseudo$-$code, you may if you wish.