enter image description here

I came across this question while solving past papers and I'm not very sure as to how to construct my proof for the second and third question. I understand the concept that can be applied here would be that the lower bound for any sorting via comparisons based algorithm is always $n\log n$.

It would be impractical to find the factorial of 12 and try to see the number of levels in the decision tree. Is there an easy way I can go about doing the same?

  • 3
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael May 16 '18 at 5:20

Computing $\lceil \log_2 12!\rceil = \lceil \log 479{,}001{,}600 \rceil = 29$ is not very difficult, even by hand. The $\log_2$ becomes easier if you recall that $2^{30} = (2^{10})^3 \approx (1{,}000)^3 = 1{,}000{,}000{,}000$.

Anyway, this gives a lower bound of $29$ for the number of comparisons you need to make. Hence, using the bound you brought up, Ben is clearly mistaken somewhere.

Is Tiffany right? It's not very easy to tell. While $29$ is provably a lower bound, it's actually a lower bound on the number of binary queries of any type that must be made to sort the 12 items. But Tiffany is restricted to only making comparison queries, so it's plausible that she might need significantly more queries to narrow things down to the exact right permutation.

As it turns out, $30$ queries is both necessary and sufficient to sort $12$ items, so Tiffany's implementation is also bugged. While mergesort witnesses that $30$ queries suffice [Knuth '98], the necessity of that many queries is far from obvious. At least initially, the matching lower bound was proved using a brute force search on a computer [Wells '64].

I'm not sure if a new, more simple proof has been discovered since, but in any case it's definitely not a-priori self-evident whether or not you should trust Tiffany.


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.