0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.


[1] Han, Y. (2002, May). Deterministic sorting in O (n log log n) time and linear space. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (pp. 602-608). ACM.

$\endgroup$
  • $\begingroup$ It seems the paper uses $\Theta(n+m)$ spaces. $\endgroup$ – xskxzr Aug 8 '18 at 0:38
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is it possible to do in $O(n \log \log n)$ space wth the time mentioned in the question. $\endgroup$ – old Aug 7 '18 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$ – xuq01 Aug 7 '18 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$ – Yuval Filmus Aug 7 '18 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$ – 6005 Aug 8 '18 at 0:14
  • 2
    $\begingroup$ That's OK, nobody understands the RAM model... $\endgroup$ – Yuval Filmus Aug 8 '18 at 0:15
0
$\begingroup$

It is possible to sort them in $O(n)$ time using $O(1)$ extra space. So yes.

$\endgroup$
  • 1
    $\begingroup$ This is for words of size $O(\log n)$, that is, when $m$ is polynomial in $n$. $\endgroup$ – Yuval Filmus Aug 8 '18 at 1:13
  • $\begingroup$ Yes, that's the word RAM model. $\endgroup$ – Pseudonym Aug 9 '18 at 5:49

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.