All those companies should be care about algorithmic runtime, it's part of performance and scalability. If you're not thinking about that then you're not writing production software.

I ask about runtime at every interview (part of "coding, data structures, and algorithms"). It is most definitely not a trivial concept - how do I define the correct solution to a problem when there are multiple approaches?

The requirements for a correct solution (even simple coding problems) include style, correctness, performance, and scalability.