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

ID: 3673224 • Letter: W

Question

We describe pivoting schemes for quicksort below. Match the pivoting schemes to the average-case complexities.(anser all these questions)

1.Pivot chosen uniformly at random.

2.Smallest element chosen as the pivot.

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

4.Largest element chosen as the pivot

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

1.Pivot chosen uniformly at random.

choose 1 from these options(n,n^3,nlog(n),n^2)

2.Smallest element chosen as the pivot.

(n,n^3,nlog(n),n^2)

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

(n,n^3,nlog(n),n^2)

4.Largest element chosen as the pivot

(n,n^3,nlog(n),n^2)

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

(n,n^3,nlog(n),n^2)

1. nlog(n)

2. n^2

3. nlog(n)

4. n^2

5. nlog(n)

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