-1

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!$

joe
  • 111
  • so the statemant is incorrect? – joe Jul 12 '18 at 09:03
  • A decision tree of $n!$ leaves cannot have $2^{n!}$ nodes ! –  Jul 12 '18 at 09:07
  • @ArnaudMortier: "The quickest route to sorting is dichotomy": what does that mean ? And how can a full binary tree of $n$ leaves have $2^n$ nodes ??? –  Jul 12 '18 at 09:12
  • @ArnaudMortier: a full tree of $n$ leaves has $2n-1$ nodes, not $2^n-1$ ! –  Jul 12 '18 at 09:37

1 Answers1

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)$.