Where do I start when a script is slow and I have no idea why?
Profile before guessing. For Python:
python -m cProfile -s cumtime script.py 2>&1 | head -25
Read the cumulative column first, not the per-call one. Nine times out of ten the top entry is a function nobody suspected, and the one you were about to optimise is at 2%.
Is an O(n log n) algorithm always better than O(n squared) here?
Only past the crossover point. With constants \(c_1\) and \(c_2\), the comparison is \(c_1 n \log n\) against \(c_2 n^2\), so the quadratic version wins while \(n < c_1 \log n / c_2\). For small n with a cache-friendly layout that boundary is often in the thousands, which is why insertion sort survives inside real sort implementations.
Rough numbers for what is fast and what is not?
The orders of magnitude, not the digits:
| Operation | Time |
|---|---|
| L1 cache reference | 1 ns |
| Main memory reference | 100 ns |
| SSD random read | 100 us |
| Round trip in a datacenter | 500 us |
| Round trip across an ocean | 150 ms |
The useful consequence: one network call costs as much as a million memory accesses, so batching calls beats optimising the code between them.
How do I know when it stops being worth it?
When you stop noticing it. If it has not surfaced a problem in six months, it is either solved or it was never the bottleneck you thought.