Any Decision tree that sorts n elements has height ?
A. Ω(log n)
B. Ω(n log n)
Correct answer is B.
Suppose we have a string “abc”. Then in worst case we have to take our decision among 6! arrangements, i.e. between “abc”, “acb”, “bac”, “bca”, “cab”, “cba”
So for n elements we have to take our decision from n! possible elements.
Now we know in a binary tree of Height ‘h’ we can have
2^(h+1) - 1 nodes at max.
So 2^(h+1) - 1 >= n!
-> h+1 >= log<2> (n!+1)
-> h>= log<2> (n!) -1
-> h>=log<2> (n!)
-> h >= nlogn (Using Stirling’s approximation, n! = (n^n)/e )
Hence option B is the Correct answer.