UTpaper

Free mock tests & test series

Question 48Asked in UGC NET Computer Science, August 2016 (Paper II & III, Selected Questions)

If there are n integers to sort, each integer has d digits, and each digit is in the set {1, 2, .... k}, radix sort can sort the numbers in:

  1. AO(k(n + d))
  2. BO(d(n + k))
  3. CO((n + k) lg d)
  4. DO((n + d) lg k)
Show answerHide answer

Correct answer: (B) O(d(n + k))

Explanation

Radix sort performs one stable counting sort per digit; each pass takes O(n + k) time and there are d digits. So n integers of d digits, each digit in {1, 2, ..., k}, are sorted in O(d(n + k)) time.

From UGC NET Computer Science PYQ, August 2016 (Paper II & III, Selected Questions)

This is question 48 of UGC NET Computer Science PYQ, August 2016 (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.