Consider the algorithm below, which accepts an array data and an integer r and returns r^th smallest value in the array. 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: r^th smallest value in data;i.e., a value in data such that exactly r - 1 other values are smaller Algorithm: FindRank (data, r) if n = 1 then return data [1] end Let pivot be a randomly selected value in data Partition data into values less than pivot and greaterthanorequalto pivot, as in QuickSort Insert the pivot in between the "small" and "large" parts of array Let p be the new location of the pivot if p = r then return pivot else if p > r then return FindRank (data[1..p - 1], r) else return FindRank (data[p + 1..n], r - p) end Prove that r - p must be between 1 and the length of data[p + 1..n], inclusive, when line 14 is executed. Prove that this algorithm returns the r^th smallest value in the array. You may assume that all elements of data are unique. 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 Theta(1) time to generate a random number, and you may ignore the possibility that the minimum value is randomly selected