Can n different numbers be sorted using radix sort (and counting sort for digits) in Θ(n) time?

Question

Can n different numbers be sorted using radix sort (and counting sort for digits) in Θ(n) time?

i would say yes. This is because radix sort processes the digits of the numbers in a fixed number of passes, each taking linear time, resulting in a total time complexity of Θ(n) have i got this right ? if not then how ?

Answer 1

If there is no constraint on the domain of the input, then: no, the time complexity is not Θ().

You write:

radix sort processes the digits of the numbers in a fixed number of passes

The number of passes is not fixed; it is determined by the input. You don't know upfront how many digits a number in the input might have. Unless you put restrictions on the input, a number might have 100 digits, 1000 digits, ... It is a variable determined by the input itself.

As Wikipedia - Radix sort puts it:

Radix sort operates in O() time, where is the number of keys, and is the key length.