8.3-4

8.3-4 Show how to sort n integers in the range $0 to n^3 -1$ in $O(n)$ time.


Let n = 10 be the no of integers to be sorted and to represent $n^3 -1$ integers we need 3 digits (ex: 0 -999 needs three digits).Each of the three digits can be represented by 0 to n-1 numbers.

The running time for radix sort is $\theta(d(n+k))$

d = 3 and k = n (0 to n-1 digits)

we have repeat the intermediate sort 3 times for 3 digits

$\theta(3(n+n))$ = $\theta(6n)$ = $\theta(n)$

the constant is absorbed by $\theta(n)$