2
$\begingroup$

Suppose there are $n$ balls with different weights and let $b$ be an integer between $2$ and $n$. There is a machine which, given a set $S\subset\{1,2,3,\dots,n\}$ of size at most $b$, can tell you the lightest ball in $S$. Goal is to sort the $n$ balls according to their weights, using only fewest queries to the machine. Find an algorithm to solve it using $c\log_b(n!)$ queries, for some constant $c$. where c is an absolute constant independent of b and n.

$\endgroup$
  • $\begingroup$ What if we solve the problem in O(1/n) time? $\endgroup$ – greenturtle3141 Oct 26 '16 at 4:40
  • $\begingroup$ how will you do that ... ? $\endgroup$ – user1815760 Oct 26 '16 at 7:19
1
$\begingroup$

Changing the base of a logarithm is equivalent with just multiplying the expression by a constant: logb(n!) = loga(n!)/loga(b).
Since loga(b) is just a constant, algorithms with the complexity of j logk(n!) for any constants j and k solve the question (we just put c = jk).
For this reason the base of algorithms is usually ignored when discussing asymptotic complexity. We are basically looking for an algorithm in O(log(n!) = O(n log(n)).

There are known algorithms to solve your problem in this time, such as MergeSort or HeapSort.

The option to use an oracle that finds smallest number in a subset of k elements (rather than 2) only improves the possible algorithms by a constant.

I like the idea of a modified MergeSort that splits the balls into k subsets, sorts each of them recursively and uses your Oracle to merge these subsets in linear time.
But again, this is only a constant improvement over regular MergeSort (the depth of the recursion is logk(n) rather than log2(n)).

$\endgroup$
  • $\begingroup$ The idea you describe is also a well-known solution, named a 'multi-way merge sort' or 'N-way merge' etc. It's been devised for external sorting in the old times of tape storage to utilize multiple (4 or more) storage units simultaneously for sorting data. See e.g. the Wikipedia article 'K-Way Merge Algorithms', a StackOverflow thread Algorithm for N-way merge, or ask Google for 'multi-way merge sort'. $\endgroup$ – CiaPan Oct 26 '16 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.