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.
O(n^2) algorithms are insidious in that they will work fine on test data, but will ruin performance when there's an unusually large input in production. They're landmines in your code.
One of the more interesting approaches I've seen lately is in Andrei Alexandrescu's "An Algebra for Expressing Time Complexity of Generic Functions" article[1]. The gist is you (or more likely, the library writer) annotate functions with their complexity guarantees then you can make static assertions about your runtime performance expectations which result in a compile time error if the algorithms/data structures being used cannot meet them. In theory that would prevent the O(n^2) landmine.
Unfortunately, it's not that simple. It's really depends on context.
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.
I don't see how this is relevant. That certainly is a bug if such a call is not a part of the algorithm. Here the function is correct in the sense that it returns as expected.
If the function was implemented as an infinite loop, would you consider the code working correctly as well? After all, the result after execution of the function is always correct (ex falso quodlibet).
An infinite loop is a loop that never ends, it'd not be possible to implement a function that's expected to return in terms of an infinite loop.
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.
> 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?
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).
Programs without specification have only surprising behaviour no bugs. As far
as I can see "reject!" does not specify complexity, so in this sense it would
be completely fine. Additionally it claims to change the array instantly every
time the block is called, which doesn't seem to give any other options than
making it at least quadratic (presuming flat representation for arrays). This
feels quite overspecified as accessing the array from within the block seems
quite unusual case to cater for.
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.
I'd love a type-system alike checking feature of a language that made you specify (and would verify) time complexity of functions
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)
I suspect the "verify" part of that is going to slam head-first into the Halting Problem, given that some of the quadratic behavior only happens (see the blog) for particular patterns of use or input data.
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)".
No. O(1) just means the algorithm always takes no more than some arbitrary, but fixed amount of time to complete, regardless of the size of the input. That fixed amount of time could be a billion years (or more).
You mean O(1) (alternatively, O(k)) -- from the definition of Big O notation, O(0) is nonsensical. But even then; O(1) just means "constant time", it does not mean "soon."
> from the definition of Big O notation, O(0) is nonsensical
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.
