From my admittedly limited experience at Google, given the size of the input data even a "small" project deals with those little algorithmic inefficiencies really add up quickly. You have to do a lot of optimizing and using clever data structures to make something work at all.

I haven't worked at any of these companies so I wouldn't know how often they're performing these computations. My conjecture is broad, of course, and a statistical suggestion at that: it seems unobjectionable to claim that for some companies the "typical application" lives in the 20%-25% "outlier" region most of the time.