# Can radix sort reach exponential time complexity?

For example, assume the input array is $$[121212,212121]$$ Say we are in base 10, so count sort will work in $$O(n)$$ time. We have 6 iterations which is approximately $$n^2$$. Is this a worst case example for radix sort?

If so, can I generalize this and say that given $$k$$ is the total number of digits, a worst case for the sort would be $$\frac{k}{2}$$ elements to sort?

Let $$n$$ be the number of integers to sort, $$M$$ be the maximum integer, and $$b$$ be the chosen base.

Each execution of counting sort will take time $$O(n + b)$$ and the number of such executions is $$O(\log_b M)$$. The total time complexity is then $$O((n+b) \log_b M)$$.

If you want to ensure that this complexity is exponential in the input size $$s$$ (which is at most $$O(n \log_2 M)$$) you need to select an exponential value of $$b$$, e.g., $$b = 2^n$$ if $$M = O(2^{\text{poly}(n)})$$.

If $$b$$ is constant (e.g., base $$10$$) then the time complexity of radix sort will always be $$O(n \log M)$$, which is always polynomial in the input size $$s = \Omega(n + \log M)$$ since $$O(n \log M) = O( (n + \log M )^2 ) = O(s^2)$$. This bound is tight when $$M = \Theta(2^n)$$.

• What about if M is unbounded? for example we have $n$ elements where $\log_bM$ is set to $n$ or $n^2$ etc. would we get $O(n^2)$ or $O(n^3)$ accordingly?
– Nix
May 10, 2020 at 13:52
• Yes. Keep in mind that $n$ is the number of input elements and not the size of the representation of the input, which is at least $\log M$ anyway. May 10, 2020 at 13:58
• And how would I counter this problem? if I change the basis to $M$ can I guarantee $O(n)$ time?
– Nix
May 10, 2020 at 14:52
• If you change the base to $M$ you'll get $O(M)$ time, i.e., you fall back into just running counting sort. I think that, asymptotically speaking, the best thing you can do is to pick $b= n^\epsilon$ for any choice of a constant $\epsilon \in (0, 1]$ (for example, pick $b=n$). In this way time required will be $O(n \frac{\log M}{\log n})$. May 10, 2020 at 15:06
• Yes I agree, also changing the basis could result in a larger time than $O(n)$ given the total number of digits is larger than $n$. Curious though, isn't there a solution for $O(n)$ complexity where $n$ denotes the number of (total) digits in the array? Or should I resort to a different algorithm altogether.
– Nix
May 10, 2020 at 17:30