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

| cite | improve this answer | |
$\endgroup$
  • $\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 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 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 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 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 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.