edited by
1,872 views

2 Answers

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

so height will be log(n!)= Ώ(nlogn)
1 votes
1 votes

Answer: C

Explanation:

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 \; \textbf C$ is the correct option.

 

edited by
Answer:

Related questions

1 votes
1 votes
1 answer
3
makhdoom ghaya asked Jul 28, 2016
3,597 views
We can show that the clique problem is $NP$-hard by proving thatCLIQUE $\leq$ P 3-CNF_SATCLIQUE $\leq$ P VERTEX_COVERCLIQUE $\leq$ P SUBSET_SUMNone of the above
1 votes
1 votes
1 answer
4
makhdoom ghaya asked Jul 28, 2016
2,016 views
Match the following $:$$\begin{array}{} & \textbf{List – I} & & \textbf{List – II} \\ \text{a.} & \text{Bucket sort} & \text{i.} & O(n^3\lg n) \\ \text{b.} & \text...