Reference no: EM132466004
Assignment - Consider the algorithm below, which accepts an array data and an integer r and returns the rth 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: rth 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 deta[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
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 | return FindRank(data[1..p - 1], r)
13 else
14 | return FindRank(data[p + 1..n], r - p)
15 end
Instructions -
1. Prove that must be between 1 and the length of, inclusive, when line 14 is executed
2. Prove that this algorithm returns the 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; 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.