3 ms·
If you count everything carefully, it's O(n / log log n) https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf https://
by hgsgm 3y ago
If you count everything carefully, it's O(n / log log n)
https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf 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 3y agoThis 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!