AT9 (Correctness vs Performance): Big-O hides constants. An O(n log n) algorithm with a large constant factor can be slower than an O(n²) algorithm with a small constant factor — for all n that occur in practice. Treating O(n log n) as equivalent to O(n) at n = 10⁹ is FM3. But treating O(n²) as equivalent to O(n log n) for n = 50 is an unnecessary optimization effort.
The practical rule: profile first, analyze second, optimize only where measurements show a problem.
The space-time duality (AT2 continued from Ch 17): Almost every technique for reducing time complexity increases space complexity. Memoization (Chapter 21) reduces O(2ⁿ) to O(n) time by paying O(n) space. Sorting reduces O(n) search to O(log n) search by paying O(n log n) time upfront. There is no free lunch.