undefined

Problem 1. Suppose we have an array A[1 : n] of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank(A[i]), as the number of elements in A that are strictly smaller than A[i] plus one; so rank(A[i]) is also the correct position of A[i] in the sorted order of A. Suppose we have an algorithm magic-pivot that given any array B[1 : m] (for any m > 0), returns an element B[i] such that m/3 q, we need to look for it in the subarray A[q +1:n] (although, what is the new rank we should look for now?). 1Such an algorithm indeed exists, but its description is rather complicated and not relevant to us in this problem. 2 Note that an algorithm with runtime O(n log n) follows immediately from part (a) sort the array and return the element at position r. The goal however is to obtain an algorithm with runtime O(n). Problem 1. Suppose we have an array A[1 : n] of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank(A[i]), as the number of elements in A that are strictly smaller than A[i] plus one; so rank(A[i]) is also the correct position of A[i] in the sorted order of A. Suppose we have an algorithm magic-pivot that given any array B[1 : m] (for any m > 0), returns an element B[i] such that m/3 q, we need to look for it in the subarray A[q +1:n] (although, what is the new rank we should look for now?). 1Such an algorithm indeed exists, but its description is rather complicated and not relevant to us in this problem. 2 Note that an algorithm with runtime O(n log n) follows immediately from part (a) sort the array and return the element at position r. The goal however is to obtain an algorithm with runtime O(n)