# Sorting n weight disks with decision tree

I was refreshing some old tests about sorting algorithms, there was a question as follow:

Question: we have n weight disks with different weights and we want to sort them pair by pair, How many times we have to weight in worst case (maximum comparisons) to sort the whole disks?

the answer was $$\lceil \log n! \rceil$$.

My issue is that I could not get to the answer and could anyone elaborate on how the answer is working?

Also one of the options was $$\lceil n\log n \rceil$$, and as we know, the order of $$\log n!$$ and $$n\log n$$ are same, So why shouldn't the ceilings be equal too?

and How does having an ordered and distinct set of size n, matter in decision tree?

• The order may be the same, but the numbers are not. $\log n! = \log n + \log(n-1) + \log (n-2) + \cdots + \log 2 < n\log n$ Mar 30, 2021 at 20:15
• @Joffan Hmm, I see, beautiful. Mar 30, 2021 at 20:19
• n log n - n log e is a better, but not perfect approximation to log n! Mar 30, 2021 at 20:22

The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $$n!$$ leaves (one for each output permutation). Each internal vertex in the decision tree represents a comparison has has $$2$$ children. This means that the height of the tree must be at least $$\log_2 n!$$. Since the height must be an integer, you can take the ceiling.
However no algorithm can attain this number of comparisons in the worst case for all values of $$n$$ (notice that the intended answer does not use the asymptotic notation). Here you can find the number of comparisons needed to sort $$n$$ elements for some small values of $$n$$. For $$n=15$$, $$\lceil \log 15! \rceil = 41$$ but $$42$$ comparisons are needed.
To answer your second question, $$\lceil n \log n \rceil$$ is incorrect since it not a valid lower bound. For example, for $$n=2$$, $$2 \log 2 = 2$$ but $$1$$ comparison is sufficient. You are right in saying that $$O(\log n!) = O(n \log n)$$ but notice how the answers are not using the big-Oh notation.