And financial companies, banks, hedge funds etc. Even the most "boring" financial companies (actuaries, insurance companies) process huge amounts of data where performance becomes critical.
We have a data base that gathers about a 5GB of market data a day and we have to run algorithms to analyse the data and analyse the behaviour of our system. Efficient algorithms become very important.
I am an engineer at Google, and basically all of the engineers I work with have to scale their software in least one dimension such that big-O complexity is a significant (and daily) concern. What I mean by "daily concern" is that the check-ins are happening on a daily basis would be noticeably inefficient if they used an O(n^2) algorithm instead of an O(n) algorithm, for example.
> Certainly, most at the non-Googlish companies hardly ever deal with this.
My main experience is Google and Amazon, so I couldn't say. I was meaning to talk mainly about Google/Amazon/Facebook/Twitter-like companies. I'm betting Palantir is also one such place.