Question

Any decision tree that sorts n elements has height

• A. $\Omega \left(logn\right)$
• B. $\Omega \left(nlogn\right)$
• C. $\Omega \left(n\right)$
• D. $\Omega (n{)}^2$

Answer 1

The correct option is B $\Omega \left(nlogn\right)$

Any comparison based sorting alogrithm for sorting 'n' elements it takes $\Omega \left(nlogn\right).$

• The depth of a decision tree for a given value of n is $\Omega \left(nlogn\right)$
• There are n! leaves. A tree of height h has at most $2^{h-1}$ nodes. So, $2^{h-1}\ge lo{g}_{2}n!=lo{g}_2(1,\mathrm{2.......}n)$

$=lo{g}_{2}1+lo{g}_{2}2+.....+lo{g}_{2}n$
$>\left(n/2\right)lo{g}_2\left(n/2\right)$

$h\in \Omega \left(nlogn\right)$