When choosing the last item of a sequence as the pivot, the QuickSort algorithm will yield its worst case performance ofO(n2)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 inO(nlog n).
Explain why Quicksort runs inO(n2)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 ofO(n2)whether pivot selection is performed using the median-of-three approach, or the pivot is selected as the last item in the sequence.
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here