3
$\begingroup$

Say you're given a set of objects, and you don't know the value of any of the objects, but, given a pair of two objects you are always told which one is bigger.

For a set $\{x_1, x_2, \cdots, x_n\}$, what is the minimum number of comparisons that will suffice to put all of its elements in ascending order of size: i.e. of the form $$\{y_1, y_2, \cdots, y_n\}$$ where $y_i\lt y_{i+1}$ for all $i$?

Obviously this is easy to determine for small $n$ (by trial and error), but as $n$ increases, I'm not sure which comparisons are redundant.

$\endgroup$
  • 3
    $\begingroup$ This is $n\log(n)$ asymptotically - well studied. See en.wikipedia.org/wiki/Sorting_algorithm. $\endgroup$ – Ethan Bolker Feb 27 '16 at 1:48
  • 1
    $\begingroup$ There are a total of $n!$ permutations, hence you need at least $\log_2 n!\sim n\log_2 n$ comparisons. $\endgroup$ – A.S. Feb 27 '16 at 2:14
  • $\begingroup$ @EthanBolker How should I turn that into an integer? Obviously $n \log (n)$ is not always a whole number. $\endgroup$ – beep-boop Feb 27 '16 at 4:00
  • $\begingroup$ @RobArthan What I mean is: what's the max number of comparisons needed to be able to list all elements of the set in order of size. $\endgroup$ – beep-boop Feb 27 '16 at 4:03
  • 2
    $\begingroup$ As of Aug 2011, the exact value of minimum number of comparision is not known for $n = 16$, see OEIS A036604. $\endgroup$ – achille hui Feb 27 '16 at 4:29

Your Answer

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

Browse other questions tagged or ask your own question.