If we let S = problem size, then after a speed-up by a factor of 10:
Complexity Problems Size Linear (n) 10S nlogn 10S (for large S) n2 3.16S n3 2.15S 2n S + 3.3
We can conclude from this that bad algorithms are not helped much by optimization.
However, clever optimizations of clever code may not improve things either. Knuth (1971) presented an amusing discussion in which he referred to an algorithm which he had developed many years ago which translated a complicated expression to fewer instructions than some other people's algorithm. Years later, he realized that programmers rarely used such complicated expressions, and it isn't worth the compiler's time to optimize them.
