COUNTING-SORT takes O(n+k) time to sort n numbers in the range 1,.., k. RADIX-SO

Question

COUNTING-SORT takes O(n+k) time to sort n numbers in the range 1,.., k. RADIX-SORT takes O(nd) time to sort n number of d digits each. By combining these two, we can get a linear running time for sorting elements from a wider range.

(a) Given a number x, show how to get the ith digit of its base-r representation in O(1) time. (the 1st digit is the least-significant one.)

(b) What is the running time of RADIX-SORT on an array of n numbers in the range 0,…,n5-1, when using base-10 representations?

(c) Given an algorithm to sort an array of n numbers in the range 0,..,n5-1 in only O(n) time. Does your technique extend to wider ranges of elements? Explain.

Explanation / Answer

Dear.. a. By the given number x, we can get the ith digit is by tackink as [x/r^i-1] and note that dividing by r^i-1 and taking the floor is just “shifting right” the base 'r' representation of x by i-1digits and taking that value mod r is just keeping the least significant remaining digit.
If we can compute r^i-1 in O(1) tme, then an algorithm for computing the ith digit is strightforward. Alterateil, we can get the digits in sequence by computing 1, r, r^2, r^3,....., which yields O(1) time per digit. b.
By using base 10, the numbers have d = logn^5 = 5 log ndigits. Each COUNTING-SORT call takes O(n+10) = O(n) time, so the running time of RADIX-SORT is O(nd) = O ( nlogn ). c. If we use base n, the numbers have d = log basen n^5 = 5 digits. And by part (a) we can compute each digit in O(1) time. Therefore each COUNTING-SORT call takes O(n+n) = O (n) time, so the running time of RADIX-SORT is O(nd) = O(n). This method extends to numbers in the range o, ....., n^c -1for any constant c. c. If we use base n, the numbers have d = log basen n^5 = 5 digits. And by part (a) we can compute each digit in O(1) time. Therefore each COUNTING-SORT call takes O(n+n) = O (n) time, so the running time of RADIX-SORT is O(nd) = O(n). This method extends to numbers in the range o, ....., n^c -1for any constant c. O(n+n) = O (n) time, so the running time of RADIX-SORT is O(nd) = O(n). This method extends to numbers in the range o, ....., n^c -1for any constant c.   

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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