2
$\begingroup$

Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is $O(n)$ because you can accomplish it by putting everything into a hashmap that maps keys to lists of equal elements.

The external memory model of computation is one where for an input size $N$ that's stored in "external memory," you can fit $M$ elements inside cache, and can transfer $B$ elements from cache to external memory per one slow I/O operation. All computation has to be done in cache.

The fastest sort in external memory is generally accepted to be an $O(N \log N)$ mergesort, even when the position in the output can be computed directly from the keys without any comparison. A surprising result shown in [1] is that, for practical[2] values of $B$ and $M$, permuting the values in external memory based on indices that are already known is no faster than sorting them! (This is in sharp contrast to permutation in RAM, which is trivially $O(n)$.)

I think grouping equal elements might be easier than permuting, because there are many permutations that would group equal elements. In a sense, if there is one "easy permutation" that groups equal elements, the algorithm could give you that instead of being forced to give you a specific permutation that may be very hard. Is this so? If it is so, what algorithm is known that could do it?

[1] https://pdfs.semanticscholar.org/05f5/c5521c69a87ed2fc32521312d85aeb1da874.pdf

[2] This is actually not true for big (>4KB) elements on solid state drives, but it's commonly repeated and valid for many cases.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Even testing whether $n$ elements are distinct is known to require $\Omega(n \log n)$ time on a model with some pretty reasonable restrictions. See, for example, Anna Lubiw, András Rácz: A Lower Bound for the Integer Element Distinctness Problem. Inf. Comput. 94(1): 83-92 (1991).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I always thought that hash sets had $O(1)$ insertion times. If I inserted $n$ elements into a hash set I would in the process be able to tell if any were equal. Does the model prevent me from using this technique to test distinctness in $O(n)$? (You might want to take a look at this paper, which claims that in the RAM model, integers can be sorted in $O(n \sqrt{\log \log n})$.) web.mit.edu/benmv/Public/thorup.pdf $\endgroup$
    – Display Name
    May 3, 2019 at 14:29
  • 3
    $\begingroup$ Read the papers carefully to see what operations are allowed. Algorithms faster than $O(n\log n)$ for sorting rely on assumptions on the sizes of the numbers, or use various bit tricks. $\endgroup$
    – Jeffrey Shallit
    May 3, 2019 at 16:17

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.