Let $U=\{1,2,3\cdots m-1\}$ and some $n$ keys from $U$. Is it possible to sort these $n$ keys in $O(n \log \log n)$ time using $O(n)$ space?
Model of computation is RAM.
3 Answers
$\begingroup$
$\endgroup$
1
The algorithm is studied by Yijie Han in his paper [1].
There's also a relevant question on cstheory: Han's $O(n\log\log n)$ time, linear space, integer sorting algorithm.
answered Aug 7, 2018 at 23:32
-
$\begingroup$ It seems the paper uses $\Theta(n+m)$ spaces. $\endgroup$– xskxzrAug 8, 2018 at 0:38
$\begingroup$
$\endgroup$
5
I think you may need to clarify your question. It is certainly not possible as written, because the running time and space usage should depend on $m$, not just on $n$.
In particular, if $m$ is very large, then $n$ numbers may take a large amount of space to write out in the first place, which immediately lower bounds the running time.
-
$\begingroup$ Is it possible to do in $O(n \log \log n)$ space wth the time mentioned in the question. $\endgroup$– oldAug 7, 2018 at 8:40
-
$\begingroup$ @old You sort a list, not a set. A set is not ordered. It is not clear what you want to sort. $\endgroup$– xuq01Aug 7, 2018 at 10:52
-
1$\begingroup$ (1) In the usual RAM model, every memory cell holds a machine word of length $O(\log N)$ bits, where $N$ is the length of the input in bits, and operations on a single machine word take $O(1)$ time. In this case, assuming the standard encoding, $N = n\log m$, and so we are allowed constant time operations on words of length $O(\log n + \log \log m)$ bits. (2) Space consumption doesn't include the input. (3) OP might have meant to use $N$ rather than $n$ in their time and space requirements. $\endgroup$ Aug 7, 2018 at 23:28
-
$\begingroup$ @YuvalFilmus Thanks for your comment, I only have a vague understanding of the RAM model so I maybe should not have answered. I upvoted your comment and your own answer for visibility. $\endgroup$– 6005Aug 8, 2018 at 0:14
-
2$\begingroup$ That's OK, nobody understands the RAM model... $\endgroup$ Aug 8, 2018 at 0:15
$\begingroup$
$\endgroup$
2
It is possible to sort them in $O(n)$ time using $O(1)$ extra space. So yes.
-
1$\begingroup$ This is for words of size $O(\log n)$, that is, when $m$ is polynomial in $n$. $\endgroup$ Aug 8, 2018 at 1:13
-