2
$\begingroup$

So i came upon this question where:

we have to sort $n$ numbers between $0$ and $n^3$ and the answer of time complexity is $\mathcal{O}(n)$ and the author solved it this way:

first we convert the base of these numbers to $n$ in $\mathcal{O}(n)$, therefore now we have numbers with maximum 3 digits.

now we use radix sort and therefore the time is $\mathcal{O}(n)$

so i have three questions :

  1. is this correct? and the best time possible?

  2. how is it possible to convert the base of n numbers in $\mathcal{O}(n)$? like $\mathcal{O}(1)$ for each number? because some previous topics in this website said its $\mathcal{O}(M(n) \log(n))$?

  3. and if this is true, then it means we can sort any $n$ numbers from $0$ to $n^m$ in $\mathcal{O}(n)$?

$\endgroup$
  • $\begingroup$ In the end, this is about $\log(n^k) \in \Theta(\log n)$ for fixed $k$. $\endgroup$ – Raphael Apr 6 '18 at 15:51
  • $\begingroup$ @Raphael this sorting problem can be solved with O(logn) ?! how? and what is that k? $\endgroup$ – John P Apr 6 '18 at 17:23
  • $\begingroup$ No, it can't. The point is that your numbers have at most constant length so you can use e.g. counting sort. (My comment may have been slightly misleading, sorry.) $\endgroup$ – Raphael Apr 6 '18 at 23:49
4
$\begingroup$

The reason of your confusion is that the computational model under which the algorithm is run is not specified.

Assuming you are allowed to perform arithmetic in $\mathcal{O}(1)$ time$^*$, then the $\mathcal{O}(mn)$ bound is correct. The reason is that you don't need to explicitly make base conversions. Since radix sort only ever compares digits of numbers, it is sufficient to provide a way to compare arbitrary digits in $\mathcal{O}(1)$ time$^{**}$; it is not hard to convince yourself that given an integer $x$, the $i$-th digit from the right in the base $b$ representation of $x$ is exactly:

$\qquad x/b^{i-1} \ \% \ b$

where $\%$ is the modulo operator.

Under more stringent conditions on arithmetic (such as classical random access machines or constantly-bounded Word-RAMs), both taking the modulo and division by a constant are operations that take logarithmic time, changing the running time of radix sort accordingly.


$^*$ For example, with a Word-RAM model with $w \ge \log n$.

$^{**}$ Notice that this is consistent with practice. If you have any sense, you would set $b$ to be a power of two in an implementation.

$\endgroup$
  • $\begingroup$ so when they don't state the attributes of our machine, can i assume that whenever i have n numbers, i can convert the base of each number in O(1) therefore converting them all will take O(n) correct? (assuming that our computer is a modern day computer and not an old one) because my whole confusing with this question was the part where we convert the base of each number in O(n) therefore making the entire algorithm work in O(n) $\endgroup$ – John P Apr 6 '18 at 11:11

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.