1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Nix
    May 10 '20 at 13:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    May 10 '20 at 13:58
  • $\begingroup$ And how would I counter this problem? if I change the basis to $M$ can I guarantee $O(n)$ time? $\endgroup$
    – Nix
    May 10 '20 at 14:52
  • $\begingroup$ 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})$. $\endgroup$
    – Steven
    May 10 '20 at 15:06
  • $\begingroup$ 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. $\endgroup$
    – Nix
    May 10 '20 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.