In class, we saw a deterministic O(n) time algorithm to compute the kth smallest element in...

   

Transcribed Image Text:

In class, we saw a deterministic O(n) time algorithm to compute the kth smallest element in an unsorted array S of n numbers. The main idea to get the linear time algorithm was to find a good pivot element. This was done by partitioning the array S into n/5 sets of size 5. Then computing the median of each of these sets of size 5, resulting in a set of n/5 medians. The pivot element is the median of these n/5 medians and is computed recursively. What if we partition the array S into n/3 elements of size 3, instead. (a (b) (c) How many elements are guaranteed to be smaller than the pivot and how many are guaranteed to be larger than the pivot? Explain your reasoning (you do not need to give a formal proof). Give the recurrence for the new running time of the algorithm. Solve the recurrence using any method of your choice and state the running time of the algorithm in terms of n using Big-Oh notation. In class, we saw a deterministic O(n) time algorithm to compute the kth smallest element in an unsorted array S of n numbers. The main idea to get the linear time algorithm was to find a good pivot element. This was done by partitioning the array S into n/5 sets of size 5. Then computing the median of each of these sets of size 5, resulting in a set of n/5 medians. The pivot element is the median of these n/5 medians and is computed recursively. What if we partition the array S into n/3 elements of size 3, instead. (a (b) (c) How many elements are guaranteed to be smaller than the pivot and how many are guaranteed to be larger than the pivot? Explain your reasoning (you do not need to give a formal proof). Give the recurrence for the new running time of the algorithm. Solve the recurrence using any method of your choice and state the running time of the algorithm in terms of n using Big-Oh notation.

Answer rating: 100% (QA)

a Guaranteed elements smallerlarger than the pivot When partitioning the array S into sets of size 3 ... View the full answer