An array has n elements and each element is an integer from the set {1,2,3,,,,k}. There is an oracle that answers anything about the array in yes or no. You only have access to the oracle and not the array. Show that the array can sorted by at most O(klog(n)) queries.
1 Answers
Since you know all of the possible values in the array, it suffices to find the frequency of each possible value. Then output the correct number of 1's, the correct number of 2's, etc.
You can achieve this in Theta(k log n) queries, all of the form:
- "Is the frequency of element
xgreater thanc?"
This amounts to doing a binary search for each of the k frequencies. Since the frequency of each element is an integer in [0, n], you can do this binary search with at most log_2(n+1)+1 queries.
Related