> 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.
But there are still informal limits. If the performance impact is bad enough, (say, 5x slower, or changing a linear algorithm to quadratic), it’s probably going to be reverted anyway. We just don‘t have any practical way of formalizing rough performance guarantees at an API boundary.