On Saturday, 5 December 2015 at 20:48:16 UTC, Andrei Alexandrescu
wrote:
On 12/04/2015 10:24 PM, Timon Gehr wrote:
In fact I went through the implementation but soon I hit a
wall: what's the _relationship_ between the two growths? It may
be the sum O(m + n) but also the product O(m * n). So the
operator must be encoded as well.
Then what do we do with more complex relationships like O((m +
n) log n) etc.
Then once you get to some reasonable formula, what's the
ordering on top of these complexities? Probably difficult.
I gave up on this for the time being. Ideas welcome.
Andrei
Well, we could see how CAS libraries handle this kind of stuff
(if there _is_ one which handles it)...
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?
