There are some important distinctions though, which gets lost if one takes the quote at face value without much context. For example, I think one should strive to avoid O(n^2) loops and similar unless one is absolutely positively certain n will forever be bounded to some sane value.
My point being that O(n^2) code can make the application completely unusable, which makes it something more than a pure optimization problem.
Bear in mind that the given quote is only the most memorable part of Knuth's longer statement:
> We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
> Yet we should not pass up our opportunities in that critical 3%.
FWIW, I've read that Knuth attributes it to Hoare, and Hoare attributes it to Knuth.
Looking now, I see that Knuth also wrote a similar comment in "Computer Programming as an Art", at http://faculty.salisbury.edu/~xswang/Research/Papers/turning... :
> The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.
That was published the same year and month as the first paper, so I don't know which gets priority for any attributions.
Then you can shave off some execution time by using a slightly different construct, though bigger wins usually lie elsewhere.