3 ms·
It's extremely unlikely that the constants would be nearly that large, but yes.
by thfuran 2y ago
It'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]