Consider the algorithm below, which accepts an array data and an integer r and returns the 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 1 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 Partition data into values less than pivot and > pivot, as in Quicksort 7 Insert the pivot in between the "small" and "large" parts of array s Let p be the new location of the pivot 9 if p = r then 10 | return pivot 11 else if p > r then 12 | return FindRank(data[1..p - 1], r) 13 else 14 | return FindRank(data[p + 1..n], r - p) 15 end 1. Prove that r - p must be between 1 and the length of data[p + 1..n], inclusive, when line 14 is executed. 2. Prove that this algorithm ret inns the r^th smallest value in the array. You may assume that all elements of data are unique. 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 theta (1) time to generate a random number, and you may ignore the possibility that the minimum value is randomly selected Consider the algorithm below, which accepts an array data and an integer r and returns the 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 1 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 Partition data into values less than pivot and > pivot, as in Quicksort 7 Insert the pivot in between the "small" and "large" parts of array s Let p be the new location of the pivot 9 if p = r then 10 | return pivot 11 else if p > r then 12 | return FindRank(data[1..p - 1], r) 13 else 14 | return FindRank(data[p + 1..n], r - p) 15 end 1. Prove that r - p must be between 1 and the length of data[p + 1..n], inclusive, when line 14 is executed. 2. Prove that this algorithm ret inns the r^th smallest value in the array. You may assume that all elements of data are unique. 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 theta (1) time to generate a random number, and you may ignore the possibility that the minimum value is randomly selected
