1
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 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, 2018 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, 2018 at 19:40
  • $\begingroup$ On the contrary, the word RAM model is supposed to be more realistic than the bit complexity model. $\endgroup$
    – Yuval Filmus
    Sep 21, 2018 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, 2018 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, 2018 at 6:13

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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, 2018 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, 2018 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$
    – Thinh D. Nguyen
    Sep 21, 2018 at 13:01
  • $\begingroup$ Well, Yuval has already pointed this out several hours ago. $\endgroup$
    – user92914
    Sep 21, 2018 at 13:21
0
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Linear is only in the case of ranges like $[1, \mathrm{constant}]$ $\endgroup$
    – Thinh D. Nguyen
    Sep 21, 2018 at 13:19
  • $\begingroup$ Same misconception from books: cs.stackexchange.com/questions/48836/… $\endgroup$
    – Thinh D. Nguyen
    Sep 21, 2018 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, 2018 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$
    – Thinh D. Nguyen
    Sep 21, 2018 at 15:25
  • $\begingroup$ You are right. I didn't realize that RAM does not support division. $\endgroup$
    – xskxzr
    Sep 21, 2018 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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