Any decision tree that sorts n elements has height
Show answerHide answer
Correct answer: (C) Ω(n lg n)
Explanation
For any comparison-based sort the decision tree has at least n! leaves, so its height is at least lg(n!) = Ω(n lg n).
From UGC NET Computer Science PYQ, December 2014 (Paper II & III, Selected Questions)
This is question 36 of UGC NET Computer Science PYQ, December 2014 (Paper II & III, Selected Questions). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.