Earlier this year I visited U of Illinois and sat in with a group of seniors who were working on a homework problem. I printed off the homework problem for myself but was not able to solve it since I had just learned about Big O notation in my high school Calculus class. I think this algorithm, if modified to select by rank instead of just top k items, might be the solution.
The problem in question is 2B:
2. (30 pts.) You are given an array A with n distinct
numbers in it, and another array B of
ranks i1 < i2 < : : : < ik. An element x of A has rank u
if there are exactly u 1 numbers in
A smaller than it. Design an algorithm that outputs the
k elements in A that have the ranks
i1; i2; : : : ; ik.
(B) (20 pts.) Describe a O(n log k) recursive algorithm
for this problem. Prove the bound
on the running time of the algorithm
Is that possible?