Can someone please answer this THIS IS THE LINK TO THE QUEST

Can someone please answer this? THIS IS THE LINK TO THE QUESTION: http://www.chegg.com/homework-help/registrar-scheduling-registrar-prominent-northeastern-univer-chapter-3.2-problem-24E-solution-9780321573513-exc

OR ITS THIS: Prove that no compare-based algorithm can build a BST using fewer than lg(N !) ~ N lg N
compares.

Solution

Hypothesis:

Decision Tree properties:

So, in the worse case the number of comparisons is equal to the height of the decision tree.

The height of the tree is at least lg(N!) because the decision tree will have N! leafs.

Proof:

Since lg(N!) >= lg(N * N (N-1) * … * N/2)

>= lg(N/2)^N/2 )

= N/2(lgN = lg2)

= N/2lgN – N/2

which is a member of (N lg N), thus proving our initial statement.