Assume we have n integers that range from 0 to n^5 -1 in value. What will be the algorithmic complexity of sorting these numbers by using Radix sort?

Question

I don't know if it is:

1. O(n)

or

2. O(5log10(n) * (n+10)) = O(nlog10n)

or

3. O(n+k)

I could be wrong, but I need to be able to compute it to figure it out. I'm real confused here. Please explain the answer and show any calculations too. Thank you.

Answer 1

If the radix base is based on n, such as base = n (5 passes) or ceil(sqrt(n)) (10 passes), time complexity is O(n), since the constants like 5 or 10 are ignored.

If the radix base is independent of n, such as some power of 2, for example 2^8 = 256, then the number of passes = ceil(log256(n^5)), and time complexity is O(n log(n)).

The question doesn't specify what is to be used for the radix base.