Can radix sort reach exponential time complexity?

Question

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?

Answer 1

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)$.