Given an array A[L.n], where we may assume that all elements are different, and k with 1sksn. We want to return the k greatest elements of AL1.n], in decreasing order. For example, with A given by (4,8,5,2,9) and k- 3, the algorithm should output the elements 9, 8, 5 (in that order). We shall investigate two algorithms for doing so: An algorithm inspired by quicksort: if n- 1 just return Al1]: otherwise we choose a pivot p, use the Dutch National Flag algorithm (or a similar one) to rearrange A into three parts: a subarray A1 of size k with elements>p, the pivot p, and a subarray A2 of size n-ki-1 with elementsp. Then . Ifk s k1 we recursively output the first k elements of A1; .If k ki+ 1 we recursively output the first k elements of A, and then p: Ifk> kit 1 we recursively output the first ki elements of Ai, next p, and finally we recursively output the first k-ki-1 elements of A2. Consider the above algorithm. Assume (which may not be realistic) that we always use the median as pivot (and spend at most linear time on choosing the pivot). Then analyze the asymptotic (worst-case) running time, as a function of n, for each of the special cases k 10 and k-n