Decision Trees Height


#1

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: