On 12/05/2015 04:52 PM, BLM768 wrote:
Well, we could see how CAS libraries handle this kind of stuff (if there _is_ one which handles it)...
CAS = ?
Really, though, with the more complex algorithms, you start running into the kinds of issues noted in the first reply to this article: http://www.perlmonks.org/?node_id=573138 Besides, is anyone actually going to specify that they need an algorithm that is O(log(n) + m^2) or whatever? Or would a function just take _two_ algorithms, assert that each is O(log(n)) and O(m^2), respectively, and then compose them itself? The complexities depend on the types of container anyway, so in general, you should get only multi-term big-O notation when you're using multiple containers (or Cartesian products of a container with itself or something like that). Can't we just make sure one container's insert() and the other container's sort() work within a certain complexity?
Well you'd need multiple terms if you want to say things like, "inserting a range into an array is O(array[].walkLength + r.walkLength)." When you insert a range in a binary search tree, the complexity would be O(log(array[].walkLength) * r.walkLength).
Part of the art here, I feel, is knowing when to stop going too crazy about this. At this point we have a nice, round system that's simple to understand and use. Making it more complex should come only with a corresponding growth in power.
Andrei
