UTpaper

Free mock tests & test series

Question 20Asked in UGC NET Computer Science, December 2015 (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 (d n k)
  2. BO (d nᵏ)
  3. CO((d + n)k)
  4. DO(d(n + k))
Show answerHide answer

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

Explanation

Consider k buckets. For each digit: (1) place each number in the appropriate bin – O(n); (2) append all the k bins sequentially – O(k). With d digits, the total is O(d(n + k)).

From UGC NET Computer Science PYQ, December 2015 (Paper II & III, Selected Questions)

This is question 20 of UGC NET Computer Science PYQ, December 2015 (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.