3 ms·
Yes it is? Asymptotic complexity is a well defined property of an algorithm. It is an output, and it doesn't match the expected output.
by ouid 10y ago
Yes it is? Asymptotic complexity is a well defined property of an algorithm. It is an output, and it doesn't match the expected output.
- jeffdavis 10y ago"reject!" is not an algorithm. It is a semantic element of the ruby language, which is implemented using an algorithm. That algorithm, in this case, is a quadratic one.
- ouid 10y agoNo, because a linear implementation of bsearch is clearly a bug.
- TheDong 10y agoIt's ruby, so the expected complexity of any line of code is "it might complete sometime in my lifetime". 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.
- aetherson 10y agoWell, probably the reason it lasted for about 4 years with no one caring is because .reject! is a fairly rarely used function.
- flukus 10y agoCan you point out where in the function definition this was defined?