4 ms·
Sometimes we forget the lower order values when considering algorithmic complexity. Not every use case is likely to see the asymptotic behaviors. Reminds me of
by mrguyorama 9y ago
Sometimes we forget the lower order values when considering algorithmic complexity. Not every use case is likely to see the asymptotic behaviors.
Reminds me of a demo by my algorithms professor. A certain sorting method (I think binary) requires picking a good pivot to keep complexity down. Picking a random pivot point generally gives good results, but results in an O(n^2) algorithm when asymptotically examined. An algorithm for "perfect" point picking (mean of means I believe) was demonstrated. It resulted in a complexity of O(n) (linear). However, the scale to the linear term was 22. Therefore, in nearly every case, picking randomly would outperform it.
I did not realize Karatsuba required such large numbers to outperform. When I first learned about it, I was under the impression that it would be more effective even for barely "large" numbers