3 ms·
Your link seems to say it has time complexity O(n)?
by anonymoushn 3y ago
Your link seems to say it has time complexity O(n)?
- hgsgm 3y agoIf 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!