UGC NET CSE | January 2017 | Part 3 | Question: 32

Question

Any decision tree that sorts n elements has height ____

• A. $\Omega (\lg \: n)$
• B. $\Omega (n)$
• C. $\Omega (n \: \lg \: n)$
• D. $\Omega (n^2)$

Comments

(3)$\Omega (n lgn)$

Answer 1

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).

Comments

Mam, please explain what is decision tree?

Answer 2

Option C

Reference : - http://courses.cs.vt.edu/~cs1044/fall02/mcpherson/notes/c12.sorting.pdf

http://www.cs.ubc.ca/~liorma/cpsc320/files/sorting-2x2.pdf

Answer 3

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.

Comments

are you sure?

Answer 4

question already answered check the link below

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