Hm, maybe it's been too long since I had some AlgoDat lectures, but I recall we learned that memory hierarchy was rather important, and that having data in cach

Hm, maybe it's been too long since I had some AlgoDat lectures, but I recall we learned that memory hierarchy was rather important, and that having data in cache can make a huge difference. Of course for the undergrad course, learning proper analysis was more important, since the whole thing about big-O is how often $STUFF happens relative to the input size (or at least that was my big take away). That $STUFF is swappable, and in the lecture we usually used "number of compares". The idea was that a student could later analyze for other things, e.g. for loads, cache-misses, page-faults, cycles or a combination thereof. You're saying yourself: "they operated with several distinct big-O's.". So, what did you do then? From a theoretical/CS point-of-view, you're just optimizing for less VM paging. There is nothing wrong about it, quite the opposite: You're demonstrating knowledge of your machines architecture, and use it to keep memory latency low - which is both a good thing. But this isn't new, or unheard of. I recently looked something up w.r.t. tree data structures, and the 1997 8th edition of Cormen, Leiserson and Rivest even mentions how bad it is to access data from a spinning disk, and how that should be reduced (I didn't read that section in detail, because that was not what I was interested in). However, maybe sometimes people forget that, or the application of their knowledge is bad (e.g. optimize for "number of compares" when memory latency is dominant). With regards to that, I really liked the article: I do a lot of runtime analysis for assembler code across various platforms, and as such I am painfully aware how complex even decades old pipelines are - it's a pain that developers tend to forget about this. On the one hand I find (parts of) the linked article funny, on the other hand it's painful that you assume all other people to be ignorant, when this is not the case. Regarding big-E: That's also not new, but probably not as popular as it should/could be. I recall a friend mentioning that part of her PhD research was energy complexity of sorting algorithms. That was ~2008.