I find it weird that the case is called a "bug" multiple times. Sure, if its o(n^2), that's a problem, but if the code works correctly at the end, it's not a bug.
There are cases where accidental quadratic complexity would definitively be considered a bug. If a fleet of GitHub servers were burning cycles due to a quadratic reject!, I'm pretty sure the engineers would classify the misbehavior as such.
No surprises for users here, which is why that bug lasted for about 4 years with noone caring.
If the documentation stated it was O(n), or benchmarks tested it was fast, then it being slow would become a bug.
As is, it's just what it is.
That algorithm, in this case, is a quadratic one.
Here the algorithm is quadratic but will, theoretically, always complete. Thus there is no bug, but a performance problem. I think that a bug is a mistake in a programme that causes erroneous behaviour.
Say if I was writing a programme which needed to make a computation which is doable only with a quadratic algorithm. Should I not write that programme at all because it'd be a bug, albeit in most cases it'd do the processing I needed?
I'd rather call this a mistake as long as the output from the function is as expected. I'm not saying that it's a negligible mistake to use a quadratic algo where there is a linear one though. Just that I doubt it is fundamentally a bug.
This only makes sense if you completely ignore context, which doesn't make any sense at all. The point/"bug"/mistake here is using a quadratic algorithm when it isn't necessary, not just the fact that the algorithm is quadratic. If something can be solved in O(1) time, it's a mistake to use an O(n) algorithm, and similarly, if something can be solved in O(2^(n!)) time, it's a mistake to use a O(9999^(n!)) algorithm (assuming constant factors are of similar orders of magnitude etc, as they are in the OP).
Though, this behaviour was changed after all which leaves me wondering how much Ruby people care about backward compatibility.
A peeve I have with Ruby is that methods in the standard library don't have defined big-O complexities. If they did, I don't think reject! would have been specified to be O(n²), and so it would be a bug.
Then in reviews its explicit when someone's doing something dumb (specifying high complexity for new algos) at compile time if a lower-complexity function calls a higher complexity one with the same sized input, or in CI when an algorithm isn't within the complexity it claims to be (experimentally)
You'd also likely want to somehow encode space complexity as well, otherwise silly things like "precompute every possible result and put it in a giant lookup table" will register as "O(1)".
Nitpick: not sure it's nonsensical. Plug g(x) = 0 into the usual definition, and you get |f(x)| ≤ k⋅0 for some k in R, which reduces to f(x) = 0. Which is not satisfiable by any nontrivial algorithm, so not very useful, but not nonsensical.