When choosing the last item of a sequence as the pivot, the QuickSort algorithm will yield its worst case performance of O(n 2 ) when it is passed a sorted list as input. Using the media-of-three...

When choosing the last item of a sequence as the pivot, the QuickSort algorithm will yield its worst case performance of
O(n²)
when it is passed a sorted list as input. Using the media-of-three approach for pivot select, the QuickSort algorithm will execute on an already-sorted list in
O(nlog n).

Explain why Quicksort runs in
O(n²)
on an already-sorted list when choosing the last item of the sequence as the pivot. You must provide a recurrence relation or recursion tree as part of your answer.

Provide an input sequence of 10 integers that, when passed to the QuickSort algorithm, would lead to the worst case running time of
O(n²)
whether pivot selection is performed using the median-of-three approach, or the pivot is selected as the last item in the sequence.