Question

Given an array A[1..n] of integers - all of whose numbers are in the range [0, n^3 − 1] give an
algorithm which sorts them in O(n) time.

Answer 1

Yes, There is algorthim by which we can sort array whoes number are in range [0,n^3-1].The idea is Radix Sort.

Algo:-

1) do the following for each digit i where i varies from least significant digit to the most significant digit

{

sort array using counting sort or any stable sorting algo according to ith digit(3 time in this case).

}

okay now let there is d digit in input array and radix sort takes 0(x*(n+b)) where b is base like in decimal system b=10. n^3-1 is the maximum number.

The value of d will be 0(3*log_b(n)) for b base (n³-1=b^d)

.so overall time complexity will be approx 0(log_b(n)*(n+b))

let base be n the overall complexity will be 0(1*(n+n)) since log_nn =1.

so overall it become 0(n).

function sort(int arr[],int n)

{

countsort(arr,n,1);//counting sort for first digit in base n.so pass exp as n⁰=1

countsort(arr,n,n);//counting sort for second digit in base n.so pass exp as n¹

countsort(arr,n,n^2);//counting sort for third digit in base n.so pass exp as n²

}

// study about radix sort and it will be more clear.