Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/05/2015 09:48 PM, Andrei Alexandrescu wrote:
> On 12/04/2015 10:24 PM, Timon Gehr wrote:
>> void foo(@(BigO.linear) int n,@(BigO.linear) int m);
>>
>> But UDAs for parameters are not supported.
>
> That's actually pretty neat and easy to work around like this:
>
> void foo(int n, int m) @(BigOParam!2(BigO.linear, BigO.linear);
>
> 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.
> ...

Some upper bounds are incomparable, so there would not be a total order. 
But that is not a problem.

> I gave up on this for the time being. Ideas welcome.
> ...

The next step up the expressiveness scale would be to have a 
sum-of-products representation.

Proof of concept (disclaimer: hacked together in the middle of the 
night, and not tested thoroughly):

http://dpaste.dzfl.pl/d1512905accd

I think this general approach is probably close to the sweet spot. (The 
implementation is not feature-complete yet, though. It would be nice if 
it supported automatically computing a new asymptotic runtime bound from 
asymptotic bounds on the arguments.)