in Algorithms edited by
6,204 views
2 votes
2 votes

Any decision tree that sorts n elements has height ____

  1. $\Omega (\lg \: n)$
  2. $\Omega (n)$
  3. $\Omega (n \: \lg \: n)$
  4. $\Omega (n^2)$
in Algorithms edited by
6.2k views

1 comment

(3)$\Omega (n lgn)$
0
0

7 Answers

5 votes
5 votes
Best answer
option 3

Any decision tree that sorts n elements has height Omega(n lg n).

 

Proof:
A binary tree of height h has <= 2^h leaves.
At least n! leaves are required for sorting.
Thus n! <= 2^h.
    h >= lg(n!) = sum_{i=2}^n lg(i) > sum_{i=n/2}^n lg(i) > sum_{i=n/2}^n lg(n/2)
      >  (n/2) lg(n/2) = Omega(n lg n).
selected by

1 comment

Mam, please explain what is decision tree?
1
1
3 votes
3 votes
0 votes
0 votes
Option A) Best case scenario is to use a balanced binary tree. And the height of a balanced binary tree of n elements is logn.

1 comment

are you sure?
0
0
0 votes
0 votes

question already answered check the link below

https://gateoverflow.in/60623/ugcnet-dec2014-iii-31

Answer:

Related questions