#2 is very important, and sadly very under valued. You'd be surprised how many candidates I interview who don't understand the basic concepts behind time complexity. I'm not even talking about big-O. I'm talking about the idea that simple algorithms are dominated by a fundamental operation, and that in order to make said algorithm faster you must reduce the number of times you perform that fundamental operation.
So when I ask "if that method were performing too slowly, what would you do in order to make it faster?" I'm often met with answers-phrased-as-questions like "use Vector instead of ArrayList?" Or often the confident statement "use HashMap" because apparently HashMap magically makes things faster... Except we ask this question about a range query (aka checking "if x < y" instead of "if x == y").
Sorry, but understanding basic data structures is not difficult. This cannot be regarded as computer science. The examples he gives ("Recursive Towers of Hanoi", ...) attract the wrong people - those who are deeply depressed after their first year as 'real-world' programmer.
I agree that understanding basic data structures shouldn't be difficult, but for a remarkable number of candidates it apparently is. Further, basic data structures is as much computer science as the "cell theory" is biology. It's a set of fundamental concepts that's quite core to computer science.
And if you were insistent on that answer you wouldn't be doing very well. Profiling a complex system to find bottlenecks is quite helpful. Profiling an implementation of an O(n) algorithm isn't going to tell you how to make it O(log(n)).
But it can tell me if the problem with typical data is with the constant, or with n. It may be that the O(log(n)) algorithm will be slower for typical input.
But yeah, I wouldn't be insistent about that on a job interview.
Because for a long time we have been able to make computers run faster. Also, with all of the levels of abstraction in programming, making the computer do less could be using a more efficient implementation of something three layers deep, which looks a lot like making the computer run faster.
I don't think you can achieve #1 without a bit of #2 and #3. Milage varies depending on what you're programming, but I think people are too quick to dismiss CS.
If you're, for example, rewriting an obviously correct but slow piece of code X into a faster but not obvious code Y, how do you know if the two are functionally identical without at least some knowledge of program algebra?
by testing and measuring performance ?
In real world it is rare that you have easy way to guess actual overall impact of your optimization.
sure you profile and go for hotspots but still it is very hard to actually understand full impact and CS algorithms are done in ideal conditions so they don't address complexity of executing environment and might be misleading path for optimization.