4 ms·
It's not a bug in the method, but it should be. A peeve I have with Ruby is that methods in the standard library don't have defined big-O complexities. If they
by parenthephobia 10y ago
It's not a bug in the method, but it should be.
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.
- lotyrin 10y agoI'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)
- al2o3cr 10y agoI 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)".