The Gateway to Computer Science Excellence
+3 votes

Any decision tree that sorts n elements has height

  1. $\Omega(n)$
  2. $\Omega(\text{lg}n)$
  3. $\Omega(n \text{lg} n)$
  4. $\Omega(n^2)$
in Algorithms by Boss (30.8k points)
edited by | 676 views

2 Answers

+3 votes
For any comparison based sorting algorithm the decision tree will have n! leaf nodes

so height will be log(n!)= Ώ(nlogn)
by Active (4.1k points)
0 votes

Answer: B


We know that the maximum nodes in a binary tree of height, $\color {red}{\mathrm h  = 2^{\mathrm h + 1} - 1} $ nodes.

Also, for $\mathrm n$ elements the decision would be taken from $\color {red}{\mathrm n!}$ elements.

 $\Rightarrow 2^{\mathrm h+1} - 1 \ge\mathrm n!\\\Rightarrow \mathrm h \ge \log_2 \mathrm n! + 1\\\Rightarrow \mathrm h \ge \log_2\mathrm n!\\\Rightarrow \mathrm h \ge\mathrm n\log\mathrm n  \;\;\;\;\;\;\text{[Using Stirling's approximation, $\mathrm n! = \frac{(\mathrm n^{\mathrm n})}{e}]$}\\\Rightarrow \Omega( \mathrm n \log\mathrm n)$

$\therefore$ B is the correct option.


by Boss (19.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,366 answers
105,265 users