I've learned over and over again that Big O is a nice theoretical model, but often doesn't translate. The famous case is std::list looking better than std::vector but almost always being worse, but I've seen plenty of others.

I work on a very large system, but spend far more time chasing down poor performance due to emergent behavior than I do worrying about Big O on some small piece.