> If the performance impact is bad enough

Even worse, it's possible to select a new algorithm that improves the best-case and average-case runtimes while degrading the worst-case runtime, so no matter what you do it will punish some users and reward others.