UTpaper

Free mock tests & test series

Question 45Asked in UGC NET Computer Science, June 2017 (Paper II & III, Selected Questions)

Any decision tree that sorts n elements has height ..............

  1. AΩ(lg n)
  2. BΩ(n)
  3. CΩ(n lg n)
  4. DΩ (n²)
Show answerHide answer

Correct answer: (C) Ω(n lg n)

Explanation

A binary tree of height h has at most 2ʰ leaves. Sorting n elements requires at least n! leaves, so n! ≤ 2ʰ, giving h ≥ lg(n!) ≥ (n/2) lg(n/2) = Ω(n lg n).

From UGC NET Computer Science PYQ, June 2017 (Paper II & III, Selected Questions)

This is question 45 of UGC NET Computer Science PYQ, June 2017 (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.