a) What is the running time of RANDOMIZED-QUICKSORT algorithm (unmodified) as given in Lecture 5 (and in the book) when applied to an array where all elements are equal (i.e., Ali]- A] for all i,j E n)? b) If we expect many equal elements in the input array, it is better for QUICKSORT to use a modified PARTITION routine that partitions subarrays with respect to the pivot z into 3 parts consisting of elements x,-x x respectively. Give such a modified PARTITION routine so that it partitions in place a subarray A|l,...r] with respect to a pivot element x- Alr] into three parts as suggested above. The routine should permute the elements of the subarray and return a pair of indices (g1,92) such that, in the final subarray all elements of Al,...qi] are smaller than the pivot x, all elements of Ali 1,...q2] are equal to x, and all elements of Ag2 +1,... r] are greater than r. a) What is the running time of RANDOMIZED-QUICKSORT algorithm (unmodified) as given in Lecture 5 (and in the book) when applied to an array where all elements are equal (i.e., Ali]- A] for all i,j E n)? b) If we expect many equal elements in the input array, it is better for QUICKSORT to use a modified PARTITION routine that partitions subarrays with respect to the pivot z into 3 parts consisting of elements x,-x x respectively. Give such a modified PARTITION routine so that it partitions in place a subarray A|l,...r] with respect to a pivot element x- Alr] into three parts as suggested above. The routine should permute the elements of the subarray and return a pair of indices (g1,92) such that, in the final subarray all elements of Al,...qi] are smaller than the pivot x, all elements of Ali 1,...q2] are equal to x, and all elements of Ag2 +1,... r] are greater than r