Question

3. (20 points) Prove the best case performance of comparison-based sortings is S2(nlgn) by using the decision tree approach as a representation of all the possible permutations of the results of sorting. FYI Stirling's approximation, n!> (n/e)".

Answer 1

Any comparison based algorithm in which at every step the output is decided by comparison result of 2 keys at a time and 2 outcome is there based on which key is minimum and which one in maximum. So in decision tree where every vertex represent comparison between 2 keys and there are 2 branches corresponding to 2 output and finally the result is obtained when we are at the leaf node.

Since n elements can be arranged in n! ways, so the decision tree will have n! number of leafs corresponding to different arrangement. Since decision tree is a binary tree with every node represent comparison between 2 keys and every edge represent the comparison result. So a binary tree with n! leaf node will have minimum height

Since the number of comparisons is equal to number of vertices in path from root node to leaf of decision tree. Therefore the height of decision tree is equal to number of comparisons needed to get the output. Since minimum height of decision tree is $n \log n$ , therefore the lower bound of comparison based sorting is $\Omega( n \log n)$ .

Please comment for any clarification.