2. (a). 3 marks] Consider sequence S below. When determining the 4-th smallest element of S using the Linear Selection algorithm with subsequences of size 5, what is the fist pivot that will be chosen? S- (9,27,4,18,19,1,21,17,8,5,111,23,6, 81,2,108,56, 29,67,43,86,32,71,31,100) (b).13 marks] After partitioning S with the above pivot, what is the next pivot to be chosen? (b). [4 marks] The recurrence relation for the running time of the median of medians algorithm on a sequence of n distinct elements, where you divide the sequence into groups of 3, can be expressed as: T(n) = 2n + T(n/3) + T(2n/3). Using the guess and test method show that NO real number c > 0 exists such that T(n) s cn for all n > 0. (i.e. it is not linear when using groups of 3.)