Question

Subject: Algorithm.

2.2 Selection- 5 points each 1. Run the simultaneous min-and-max algorithm on the array A 4, 2, 12, 6, 13,9,15). (16, 7, 10, 1,5, 11,3,8, 14, 2. Explain why the above algorithm is better than the naive algorithm for finding minimum and maximum separately. How many comparisons does the naive algorithm do? How many comparisons does the simultaneous min and max do? 3. Use the randomized select algorithm based on partition to find the median of A (4,2, 12,6, 13,9, 15) . What is the worst case time complexity for the randomized select algo- rithm? What is its average case time? Why is its average case time much better than its worst case time?

solve only part 3 and 4 please.

Answer 1

3. Randomized algorithm will select random element as pivot and partition the array A accordingly with one partition contains all elements less than equal to pivot while another will have all elements greater than the pivot. So lets say the random element selected as pivot is 13 and hence the partition of array based on element 6 will contain array A1 = {4,2,6,9,12,13} and A2={15}.

Since size of A1 is greater than (7+1)/2 = 4 I.e. rank of median hence we will find median by finding element of rank 4 in array A1.

Lets select element 9 as pivot in array A1. This will partition the array A1 as A11={4,2,6,9} and A12={12,13} since size of A11 is 4, which is rank of median, this means our pivot element was median. Hence element 9 is the median.

4. Worst case time complexity of finding median will O(n²) while the average case time complexity is O(n).

The reason of much better average case time complexity is that in most cases pivot element partitions the array such that ratio of size of left and right partition is independent of value n I.e. both partitions are almost even and hence average case time complexity becomes O(n) but in worst case the pivot element can partition the array very uneven such that size of bigger subarray is less than size of original array by constant value. Hence this will give time complexity of O(n²) but this situation is very unlikely to happen.

Please comment for any clarification.