q31,p3,d14. Any decision tree that sorts n elements has height

(A) Ω(n)

(B) Ω(lgn)

(C) Ω(nlgn)

(D) Ω(n²)

 Answer C

Explanation.

Since the height of the decision tree is Ω(nlgn).

Ex a,b,c are to be sorted.

Total 5 comarisons 3 x(log3).

In worst case height of decision tree is the complexity of sort.