I agree to some extent, and even wrote an op-ed along those lines a few years ago [1]. The issue with asymptotic algorithmic analysis isn't only the constant-fa

I agree to some extent, and even wrote an op-ed along those lines a few years ago [1]. The issue with asymptotic algorithmic analysis isn't only the constant-factors-matter one (which most people are aware of), but also that some heuristic algorithms are so good that they change the shape of the curve in typical usage, not only the constant offset. In practice, some problems that are supposed to scale as n^2 or n^3 or 2^n actually seem to scale linearly or sublinearly in practice. So asymptotic analysis can be a poor guide to algorithm selection in many places where it's used. On the other hand, I think recent trends are making worst-case analysis more relevant than it used to be, giving it something of a new lease on life. Many algorithms are now network-exposed in some form, in which a user can ultimately dictate or at least influence aspects of the input. That means a lot of systems need to worry about maliciously chosen input, or at least it's safer to build them under the assumption that they do. That's why Google wrote RE2 rather than using PCRE, for example. PCRE generally has good performance on real-world regexes, but it can be fairly easily forced into exponential performance if an adversary gets to pick the regex. That could conceivably be an issue for SAT-solving systems as well, if the problem comes directly or indirectly from a user. They typically run quickly on "natural" SAT problems derived from real-world situations, but it's also known how to purposely generate likely-to-be hard problems [2]. [1] http://www.kmjn.org/notes/nphard_not_always_hard.html http://www.kmjn.org/notes/nphard_not_always_hard.html [2] https://fenix.tecnico.ulisboa.pt/downloadFile/3779577376868/Selman95.pdf https://fenix.tecnico.ulisboa.pt/downloadFile/3779577376868/...