Knowing WHEN to do BigO optimizations is part of knowing how to optimize. And for cases that _could_ ble NlogN, it may be perfectly fine to chose N^2 for moderate N, while N^3 can kill the solution.

As for timeouts, IO and deadlocks, those problems can also be a case of poor up front optimization (before codigng).