> For instance, if n = 2^1000, the ratio of the leading expressions n lg n and n (lg n)^(11/12) is 1000^(1/12) ≈ 1.78, ignoring constants and lower-order terms. This is not a measured speedup.
Isn't it likely that the constant factor slowdown of an apparently more complicated algorithm will dominate 1.78?
> The constants in the formal construction are enormous, so this does not establish a practical speedup.
throwway262515 · · focus · HN ↗
Isn't it likely that the constant factor slowdown of an apparently more complicated algorithm will dominate 1.78?
> The constants in the formal construction are enormous, so this does not establish a practical speedup.
A pity the author stopped here.