3 ms·
Isn’t the problem that the scaling behavior only dominates with infinite n? If you have a constant factor, that doesn’t go into the scaling rule, so having som
by echoangle 2y ago
Isn’t the problem that the scaling behavior only dominates with infinite n?
If you have a constant factor, that doesn’t go into the scaling rule, so having something scale (log x)2 could still be 100 times more expensive than something that scales linearly with x for all x smaller than 2^100.
- thfuran 2y agoIt's extremely unlikely that the constants would be nearly that large, but yes.
- kragen 2y agoThere are practically important algorithms like this. There are three linear-time algorithms for constructing a suffix array, but all of them have rather large constant factors. Packrat parsing is linear in the size of the input string, but can easily execute more than 100 instructions per byte. And there are numerous theoretically asymptotically superior algorithms whose constant factors are too high for them to be useful at all, the so-called "galactic algorithms", https://en.m.wikipedia.org/wiki/Galactic_algorithm https://en.m.wikipedia.org/wiki/Galactic_algorithm. There is nothing in the article suggesting that this is such a case, however.
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]