It's an issue where processing something took O(n) time, when an algorithm to process it asymptotically more quickly (say O(log n)) would be more appropriate.

It's an issue where processing something took O(n) time, when an algorithm to process it asymptotically more quickly (say O(log n)) would be more appropriate. The old code probably works properly for the average case, but will really blow up on pathological cases. My best personal example was an optimisation pass that turned out to be exponential in the worst case. On average `n` was small, so no-one cared, until a pathological case came up where compile time ballooned to over half-an-hour. Working out that the operation could be done in a linear way only shaved a fraction of a second off the average case, but brought the half-hour case down to a few seconds.