I don’t know. I generally haven’t seen these be a problem. I think I’ve seen accidental n^2 complexity a couple of times at most and it wasn’t code written by juniors but rather just an oversight in adding nested loops somewhere they didn’t need to be. Now I have seen juniors who couldn’t figure out what was n^2 and how to fix it when given it in an interview, but slowness and big-o being related is generally rare. As you mention poorly considered sequences of network calls are more common). Additionally, the relation between the big o of a data structure and the big o of the overall algorithm solving some higher level problem tends to be more decoupled except for some very specific problem domains. I’m a systems engineer having worked in OS, embedded, mobile, and distributed systems and have seen big-O analysis of the high level code documented about 0 times (and it would have been helpful about as many).

Again, not saying it’s irrelevant and it might be highly relevant in some problem domains. But in general big-O of the common data structures should be memorized with the rest being trivia that should be accessible in the documentation for the data structure (or by looking at the implementation and doing it yourself).