Re:Static search trees: 40x faster than binary search
by ryao on Tuesday December 31, 2024 @11:24PM
(#42563938)
He is improving the constant factor in big O notation. University algorithm classes tend to ignore cases where the constant factor difference is significant enough to favor a asymptomatically slower algorithm. Matrix multiplication is the quintessential example of this, since a good implementation of the O(n^3) algorithm will outperform asymptotically faster algorithms, such as the famous O(n^2 * log(n) * log(log(n))) one that uses the FFT. At least, it outperforms it on matrix multiplications people actually do in practice.
[ Parent
| on HN ]
There are no comments on this comment yet.