(40pts) In this question, we explain why quick sort is faster than merge sort in usual cases. We saw that the running time recurrence of merge sort is 2. T(n) - 2T-+n The rightmost term n comes from merging two sorted arrays of n/2 elements. This is done in O(n) time but not too efficiently: We need to save the merged sequence in another array, and copy it back to A[1 to n] before returning A as the output. Considering this, we express the running time of merge sort by where bi > 0 is a not too small constant. Merge sort always split A into halves to perform the merge operation, so (I) describes the average case behavior also. The average case running time recurrence of quick sort is (II) T(n)s- > (T(k) + T(n -k -1) b2n) k=0 Here the last summand is changed into b2n from n-1 given in class: n-1 came from comparing the pivoting element x with every other element in A and moving in A, so it is done quicker than the merge operation of merge sort. The required time is at most b2n for some constant b2 > 0 smaller than b,. Answer the three questions regarding (1) and (lI). a) Show that (I) means T(n) s cin Inn for some c1 > 0 and all n 2 10. The number c1 must be minimum, expressed in terms of b, (You can just assume the base case: T(n)s c,nlog n is true if n 0 and all n 2 10. The number c2 must be minimum, expressed in terms of b2. (You can just assume the base case: T(n)S c2n logn is true if n 3b2 d) With the above results, argue why quick sort is faster in practice in usual cases