3 ms·
Quadratic algorithms are useless because performance matters? That is a textbook false dichotomy. Performance obviously matters, but the time hierarchy theorems
by baddox 16y ago
Quadratic algorithms are useless because performance matters? That is a textbook false dichotomy. Performance obviously matters, but the time hierarchy theorems suggest that there is certainly legitimate computation that requires quadratic time. Max flow will need at least quadratic time.
- mzl 16y agoThere are lots of algorithms with very high time-compleity that are still usefull in practice. One nice example is the decision-algorithm for Presburger arithmetic which runs in O(2^2^n).