4 ms·
O(n^2) algorithms are insidious in that they will work fine on test data, but will ruin performance when there's an unusually large input in production. They're
by pdw 10y ago
O(n^2) algorithms are insidious in that they will work fine on test data, but will ruin performance when there's an unusually large input in production. They're landmines in your code.
- eco 10y agoOne of the more interesting approaches I've seen lately is in Andrei Alexandrescu's "An Algebra for Expressing Time Complexity of Generic Functions" article[1]. The gist is you (or more likely, the library writer) annotate functions with their complexity guarantees then you can make static assertions about your runtime performance expectations which result in a compile time error if the algorithms/data structures being used cannot meet them. In theory that would prevent the O(n^2) landmine. 1. http://erdani.com/d/bigo.html http://erdani.com/d/bigo.html
- throwaway1579 10y agoYou do know that the most popular general-purpose, comparison-based sorting algorithm quicksort has a worst case complexity of O(n^2), right?
- minitech 10y agoGood implementations tend to address this with introspection, randomization, etc..
- gkya 10y agoCertainly. But does it make it a bug?
- zerr 10y agoAlternatively, it will ruin performance on artificially large test data, but will work fine in production :)