3 ms·
After a few years working on real-world code, I understood that faster asymptotic complexity was often slower on average. After a few more years working on rea
by Zarel 7y ago
After a few years working on real-world code, I understood that faster asymptotic complexity was often slower on average.
After a few more years working on real-world code, I understood that it's usually better to choose the algorithm with better asymptotic complexity, anyway.
Like, sure, my O(n) algorithm will be 10x slower than your O(n^2) algorithm for small n. But users aren't going to notice a few microseconds. Users ARE going to notice my O(n) algorithm being 100000x faster for large n, when it's the difference between milliseconds and minutes.
- 3pt14159 7y agoIt's a tough call sometimes. Code legibility is important and an O(n^2) is so often fast enough (microseconds!) that a more complex algorithm may be faster for the 0.001%ile and you're right that sometimes that means we should select it, because it makes the worst case still microseconds, but realistically speaking some codepaths change frequently enough that the true metric of a codebase is how easily it's adapted, understood, or modified. Let the guy with the big n eat cake, so to speak.