thank you very much

Problem 4. (30 points) Design an efficient algorithm for finding k pairs of elements (xi,yi) for each integer i in the range 1ik in an array A[1..n] such that xi is the i-th largest element in the array and yi is the ith smallest element in the array. Let a positive constant d be an upper bound on the cost of executing any line once in the algorithm. Note that your algorithm is not efficient if its worst-case running time is in (kn). The procedure heading for the algorithm is KMAXMIN(A,n,B,C,k), where A[1..n] is an input array of n elements, B[1..k] is an output array of the k largest elements, C[1..k] is an output array of the k smallest elements, with B[i]=xi and C[i]=yi for each integer i in the range 1ik. You can use algorithms learned in class as subroutines in your algorithm. - Give a brief high-level description and justification of your algorithm in English. - Express your algorithm precisely in pseudocode. - Clearly and rigorously derive a tight upper bound f(n) on the worst-case running time. - Obtain a tight big O upper bound for f(n) by following the definition of the big O notation