I find that big-O is exactly the performance problem that remains after you've tuned your IO, picked sensible timeouts, and eliminated deadlocks (which are straight-up bugs).

The things you list are the low-hanging fruit, after which most engineering teams throw their arms up and say "I guess we've gone as far as we can on this!"