The Gateway to Computer Science Excellence

+3 votes

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

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,366 answers

198,496 comments

105,265 users