given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them?

The answer is $O(n)$ but I don't understand this. of course counting sort itself is irrelevant, perhaps radix sort with base changing is the way to go, but I'm not sure of to change the base of $n\log n$.

  • 1
    $\begingroup$ each number has O(log n + log log n) = O(log n) bits, so radix sort requires O(log n) passes. I think the answer is incorrect since authors forgot about this part of equation. Overall, radix sort is O(n) only for fixed-size numbers. $\endgroup$
    – Bulat
    Sep 20 '18 at 18:29
  • $\begingroup$ OTOH, if you process O(log n) bits on each pass, you will need to use fixed number of passes. This means using O(n) extra memory, so why not? Anyway it's pure theory which is far from real setting $\endgroup$
    – Bulat
    Sep 20 '18 at 19:40
  • $\begingroup$ On the contrary, the word RAM model is supposed to be more realistic than the bit complexity model. $\endgroup$ Sep 21 '18 at 4:23
  • $\begingroup$ @YuvalFilmus how it works with numbers in given range? Is it suppose that each cell can hold arbitrary number? Or that each cell can hold fixed number of bits? By unrealistic I mean that radix sort on real computers became much slower when you use more than ~~256 bins in radix sort. So on real computers you will use 256 bins or so, in theoretical setting you may use O(log n) bits $\endgroup$
    – Bulat
    Sep 21 '18 at 6:07
  • $\begingroup$ @YuvalFilmus already found "By definition: A register is a location with both an address (a unique, distinguishable designation/locator equivalent to a natural number) and a content – a single natural number" --- of course, ability to hold ARBITRARY natural number is completely unrealistic $\endgroup$
    – Bulat
    Sep 21 '18 at 6:13

Note in the RAM model, indirection always takes constant time regardless of how large the address is, so each process of radix sort with base $b$ takes $O(n+b)$ time. As a result, the radix sort takes $O((n+b)\log_b(n\log n))=O((n+b)\log_b n)$ time. Choosing $b=n$ makes the asymptotic time linear.

Edit: as suggested by Thinh D. Nguyen, since extracting each digit under base $b$ requires division and modular arithmetic, which are not supported by the standard RAM model, we may want to use the word RAM model instead.

  • $\begingroup$ b=n means counting sort. But you don't need to go that far, any b^const=n will suffice $\endgroup$
    – Bulat
    Sep 21 '18 at 6:11
  • $\begingroup$ oh, I was wrong. b=n means two passes, each with n bins, since n log n < n^2. Now the book answer finally makes sense for me! $\endgroup$
    – Bulat
    Sep 21 '18 at 7:55
  • $\begingroup$ Though RAM model is historically important to the theory of computation from 20th century. It is Word RAM model that is widely used in the algorithm community. Yijie Han's nearly-linear deterministic sorting algorithm is given in this model. $\endgroup$ Sep 21 '18 at 13:01
  • $\begingroup$ Well, Yuval has already pointed this out several hours ago. $\endgroup$
    – user92914
    Sep 21 '18 at 13:21

Theoretically, there is no linear sorting algorithm if you consider only nice standard RAM model like (RAM model that was used to define recursive function and more recent model like Word RAM model).

Radix sort cannot help. Since pushing up the base to $b=n$ like in the answer of xskxzr, you need to extract the $b$-base digits.

In any theoretical RAM model, bitwise arithmetics are constant-time. Taking modulo an $O(\log(n))$-long number like $b=n$ is cumbersome.

One last note: if you still think that this can be done in linear time. That is OK, but it will never be a mathematical theorem. For otherwise, sorting with number in $[1, n^{O(1)}]$ can be done in linear time with radix sort from the very beginning of every algorithm course even in the $O(\log(n))$ word RAM model. But, that is just wrong. One cannot ignore the $polylog(n)$ overhead to simulate modular arithmetics. For students without sharp theoretical minds, that is acceptable.

For an algorithm course, one can assume unit-cost RAM. That helps students to understand the big picture and neglect the details in time bounds analysis.

  • $\begingroup$ Linear is only in the case of ranges like $[1, \mathrm{constant}]$ $\endgroup$ Sep 21 '18 at 13:19
  • $\begingroup$ Same misconception from books: cs.stackexchange.com/questions/48836/… $\endgroup$ Sep 21 '18 at 13:29
  • 1
    $\begingroup$ What do you mean by "nice"? "Taking modulo an $O(\log(n))$-long number like $b=n$ is cumbersome" I think this is from a practical view, not a theoretical view. Theoretically, a RAM or word RAM is able to take modulo an $O(\log(n))$-long number in constant time. $\endgroup$
    – xskxzr
    Sep 21 '18 at 13:57
  • $\begingroup$ Never mind the speed of CPU instructions here. Both RAM model and Word RAM model have no MOD instruction. You have to simulate it in $polylog(n)$ time. $\endgroup$ Sep 21 '18 at 15:25
  • $\begingroup$ You are right. I didn't realize that RAM does not support division. $\endgroup$
    – xskxzr
    Sep 21 '18 at 15:42

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.