In Radix Sort, where the maximum number of digits of an input numbe (integer) is

Question

In Radix Sort, where the maximum number of digits of an input numbe (integer) is 3 (i.e., k = 3), the number of bins is r, and the number of keys is n, compare asymptotic complexity in for the following two cases: (1) when the original algorithm of radix sort is used; and (2) when the radix sort is modified by sorting based on the maximum digit with k = 3 first and then by sorting of a sublist in each bin. In (2), use the asymptotic complexity for the sorting of a sublist in each bin with (nlogn).

Explanation / Answer

1) the original algorithm radix sort time complexity is O(nk)..

2) the asymptotic complexity sirting of the sub list is changed to O(nlog n), then time complexity of radix sort is O(n*nlogn)==> O(n2logn)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.