We describe pivoting schemes for quicksort below. Match the pivoting schemes to

ID: 3672208 • Letter: W

Question

We describe pivoting schemes for quicksort below. Match the pivoting schemes to the average-case complexities.

Pivot chosen uniformly at random.

Smallest element chosen as the pivot.

Median of 5 medians chosen as pivot, wherein the median is computed using randomized pivoting scheme.

Largest element chosen as the pivot

Median chosen as the pivot, wherein the median is computed using quick select with randomized pivoting.

Pivot chosen uniformly at random.

Answer 1Choose...nn^3n log(n)n^2

Smallest element chosen as the pivot.

Answer 2Choose...nn^3n log(n)n^2

Median of 5 medians chosen as pivot, wherein the median is computed using randomized pivoting scheme.

Answer 3Choose...nn^3n log(n)n^2

Largest element chosen as the pivot

Answer 4Choose...nn^3n log(n)n^2

Median chosen as the pivot, wherein the median is computed using quick select with randomized pivoting.

Answer 5Choose...nn^3n log(n)n^2

The quick sort time complexity analysis:

Algorithm description of the quick sort:

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.