I think it's really interesting how complexity theory sort of falls apart in the face of hardware-specifics and concrete use cases. The motto in computer architecture is to make the common case fast (it's in like every textbook), whereas the motto in computer science is to make the program scale/to solve generically. When push comes to shove (as this article shows), the computer architects seem to have the final word, at least when it comes to making things go more brrrrrr.
There's so much stress and attention given to complexity theory for software engineers, to the point that people will cram for hours to make it through FAANG interviews. I understand that it's important and it's just something that everyone has to go through... but data structure and algorithm performance is a Wikipedia search away, and then you choose the appropriate STL container and move on with your life. The same can't be said for gaining an understanding of modern processors.
I'm not saying that one is more important than the other or vice-versa, I'm just saying that it seems wrong to me that not knowing algorithms and data structures can break an interview, whereas not knowing hardware is virtually a non-factor.
The big take away for me is this: if you're not benchmarking, you're cargo culting.
I think you are wrong. Yes, better understanding of hardware implementation (cache sizes and latency, branch prediction and pipelines, specialized instructions) is important. But also in real life those asymptotic complexities will often have similar c and N_0, or your input will be bigger than N_0, so O(n) vs O(n^2) will still matter. Basic analysis of algorithms makes your life easier because, in this simplified model, you can get a rough estimate of time/space requirements. Of course, if you have competing implementations, you will benchmark them (which is not straightforward to do properly).
By the way, usually we use "complexity theory" for a part of theoretical computer science (math) concerned with proving lower bounds (like the most famous P vs. NP). What is required for basic analysis of algorithms (without any fancy methods) is not very hard. Yes, you can search the web like we all do, but first you need to know what are you searching for. Also, we reuse algorithms/data structures but not only in the final product but also in our own new algorightms so you cannot search it.
Regarding interviews, I think the main problem is that many companies and interviewers try to blindly copy the questions (cargo cult) without understanding the point of such interviews. The point IMO is that you evaluate analytic skills of a candidate. Correct/incorrect answer is not everything. You could do the same with math, science problems but algorithms/data structures are closer to programming. Anyway, I feel this is becoming a controversial topic.
in the 80s, alongside ibm, cray, heimdall, amdal, hitachi, etc etc you had the volume generics - intel. the generic overtook the custom, enough so the revenue and economy of scale won big. it came accompanied with a sci mindset of functional perf, * / ÷ / ^ / sqrt, rather than tps or $/transaction.
The big iron was a product of large-data-volume business problems - payroll, airline reservations, insurance quotes, credit cards, catalog order stats.
There's so much stress and attention given to complexity theory for software engineers, to the point that people will cram for hours to make it through FAANG interviews. I understand that it's important and it's just something that everyone has to go through... but data structure and algorithm performance is a Wikipedia search away, and then you choose the appropriate STL container and move on with your life. The same can't be said for gaining an understanding of modern processors.
I'm not saying that one is more important than the other or vice-versa, I'm just saying that it seems wrong to me that not knowing algorithms and data structures can break an interview, whereas not knowing hardware is virtually a non-factor.
The big take away for me is this: if you're not benchmarking, you're cargo culting.