Consider the algorithm below, which accepts an array data and an integer r and returns the r^th smallest value in the array

3. What is the average case time complexity for this algorithm to find the minimum value in an array of length n; i.e., FindRank(data, 1)? You may assume that it takes (1) time to generate a random number, and you may ignore the possibility that the minimum value is randomly selected to be the pivot. Hint: consider how large the recursive call(s) will be on average.

Input: data: array of integers Input: n: size of data Input: r: desired rank to search for: must be between 1 and n, inclusive output: rth smallest value in data i e., a value in data such that exactly r 1 other values are smaller Algorithm: FindRank(data, r) 2 if n 1 then 3 return data [1] 4 end 5 Let pivot be a randomly selected value in data 6 tition data into values less than pivot and 2 pivot, as in QuickSort 7 Insert the pivot in between the "small" and "large parts of array 8 Let p be the new location of the pivot 9 if p r then 10 return pivot 11 else if p r then 12 l return FindRank(data 1.p 1], r) 13 else 14 l return FindRank(datalp +1..n], r p) 15 end