[hgsgm]

If you count everything carefully, it's O(n / log log n)

https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-...

They are essentially the same in all conceivable practical cases in this Universe.

log log (atoms in universe) < 100

[anonymoushn]

This seems to be a matter of the above source reporting a variation of the algorithm that is asymptotically slower than the algorithm given in the paper *and* uses asymptotically more memory. Thanks for posting the paper!