The algorithm S(A, n, i) selects all the j-th smallest elements (with j i) from an array A of n elements, by using linearselect to select each of the j-th smallest elements (with j i). Clearly, one could also implement S alternatively as T(A, n, i), which first sort A (on average-case and on worstcase, the sorting takes time O(n log n) using mergesort) and then select the first i elements. Please compare the average-case complexities of the two algorithms; i.e., For the average-case complexities, under what conditions (on the choices for i), S is better than T or vice versa.

2. (not so easy) The algorithm S(A, n, i) selects all the j-th smallest elements (with j