I agree on the last point. I think this sort of stuff
can be learned in an apprentice-type way, but not many positions currently do a good job of it. A great motivated way to learn big-O type analysis, for example, is to work on a system where a bottleneck gets improved from an O(n^2) to an O(n logn) algorithm, while working alongside someone who explains to you what that means, how you determined which algorithm was which, and why this is useful analysis to know how to do.
A lot of non-degree programming jobs seem to lack both the challenge and the mentoring to make that happen, though, so you end up with people who learn more about how to bang scripts together out of snippets pulled off the web. That's actually also a pretty useful skill, especially if you become a very fast and skilled applier of band-aids, but it's not quite the same as a CS apprenticeship.
