number of nodes in a decision tree

Question

I don't know how to prove/disprove this:

In a decision tree for sort algorithm there are at least $2^{n!}$ nodes. I know that the number of leaves is $n!$

Answer 1

A sorting algorithm is able to identify any permutation of a sorted array of $n$ elements, and there are $n!$ such permutations.

Hence, assuming that we can always choose decisions that halve the subset of possible permutations, the height of the decision tree won't exceed $\lceil\log_2n!\rceil$, corresponding to a complete tree of $2^{\lceil\log_2n!\rceil}-1$ nodes.

---

As it turns out that we do have worst-case $O(n\log n)$ sorting algorithm (such as HeapSort), $\Theta(\lceil\log_2n!\rceil)$ is a tight bound for the height.

This corresponds to $2^{\Theta(\lceil\log_2n!\rceil)}=O(n!^c)$ nodes for some $c$. Using results for Heapsort, the upper bound of the decision tree must be no worse than $O(n!^2)$.