search
Log In
3 votes
874 views

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
edited by
874 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)
0 votes

Answer: B

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$ B is the correct option.

 

0
(b) option says logn , you mean to say  option (c).
Answer:

Related questions

1 vote
2 answers
1
660 views
Consider the problem of a chain $<A_{1}, A_{2}, A_{3}>$ of three matrices. Suppose that the dimensions of the matrices are $10 \times 100$, $100 \times 5$ and $5 \times 50$ respectively. There are two different ways of parenthesization : (i) ... $5$ $10$ $20$ $100$
asked Jul 28, 2016 in Algorithms makhdoom ghaya 660 views
1 vote
1 answer
2
1.7k views
Dijkstra algorithm, which solves the single-source shortest--paths problem, is a _______, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices, is a ________. Greedy algorithm, Divide-conquer algorithm Divide-conquer algorithm, Greedy algorithm Greedy algorithm, Dynamic programming algorithm Dynamic programming algorithm, Greedy algorithm
asked Jul 28, 2016 in Algorithms makhdoom ghaya 1.7k views
1 vote
1 answer
3
1.4k views
We can show that the clique problem is $NP$-hard by proving that CLIQUE $\leq$ P 3-CNF_SAT CLIQUE $\leq$ P VERTEX_COVER CLIQUE $\leq$ P SUBSET_SUM None of the above
asked Jul 28, 2016 in Algorithms makhdoom ghaya 1.4k views
1 vote
1 answer
4
945 views
Match the following : $\begin{array}{|c|l|c|l|} \hline& \textbf{List-I} & {} & \textbf{List-II} \\\hline a. & \text{Bucket sort} & i. & \text{$O(n^3\lg n)$} \\\hline b. & \text{Matrix chain multiplication} & ii. & \text{$O(n^3)$} \\ \hline c. & \text{Huffman codes} & iii. & \text{$O(n\ ... Codes : a-iv, b-ii, c-i, d-iii a-ii, b-iv, c-i, d-iii a-iv, b-ii, c-iii, d-i a-iii, b-ii, c-iv, d-i
asked Jul 28, 2016 in Algorithms makhdoom ghaya 945 views
...