To me, I would have called that an "O(n^2)" (or whatever the proper non-linear order is) issue. The issue isn't that the algorithm is O(n), but that it's not O(

To me, I would have called that an "O(n^2)" (or whatever the proper non-linear order is) issue. The issue isn't that the algorithm is O(n), but that it's not O(n) when it could be! The other interpretations by andrewaylett and daveguy seem to be more accurate (and also agrees with my own thinking). But I could also see it being used for "the asymptotic complexity was hiding a huge constant". Have you heard your interpretation used in the wild?