3 ms·
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
by lotyrin 10y ago
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)
- 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)".