All Questions
2
questions
2
votes
1
answer
1k
views
A decision tree has an expected depth of at least $\log n!$
I am looking at the proof of the following theorem and I have some questions.
The theorem is the following:
On the assumption that all permutations of a sequence of $n$ elements are equally ...
- 14k
2
votes
2
answers
8k
views
The decision tree has height at least $\log n!$
The proof of the theorem
Any decision tree that sorts $n$ distinct elements has height at least $\log n!$
is the following:
Since the result of sorting $n$ elements can be any one of the $n!$ ...
- 14k