Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I want to find out the order to comparing $n$($n$ is very big like an million) apples(weight different for each apple) with no other information, but no limition of apples putting on the balance at a time, Find out the best corresponding comparing method (with the least number of comparing) with the computation complexity, I know the part of the answer from an article, the computation complexity is $O(n \log_2 n)$, explain how to derive the comparing method with the complexity.

It is from a article written in Chinese by a Chinese-American professor, but I have no hope in translating the whole article, so I rather to mention the most important part.

share|improve this question
You should at least specify what measurements can be performed. –  Niels Diepeveen Feb 13 '12 at 23:46
Well, can you just compare just two apples at a time, or is there more to it? In other words, is en.wikipedia.org/wiki/Comparison_sort relevant to your question? –  Niels Diepeveen Feb 14 '12 at 0:00
@NielsDiepeveen - Thanks for your help –  Victor Feb 14 '12 at 0:04
I think (and Victor, please tell me if this is right or wrong!) that the 'catch' in the problem is that we have a balance and can thusly make, not just 'pointwise' comparisons, but also sum comparisons (e.g., weigh half the apples against the other half). It's still easy to show by decision-tree methods that $\Omega(n\log n)$ comparisons have to be made, so this doesn't really get you much over apple-by-apple methods, but that might not be obvious at first glance... –  Steven Stadnicki Feb 14 '12 at 0:48
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.