Any Decision tree that sorts n elements has height ?

A. Ω(log n)

B. Ω(n log n)

C. Ω(n^2)

D. Ω(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.

**References:**