Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

Timon Gehr <timon.gehr at gmx.ch> wrote:
> 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.)
> 

Brilliant! My wife has a work emergency so I've been with the kids all day,
but here's what can be done to make this simpler. 

Use D parsing and eliminate the whole parsing routine. Add multiply and
power are all defined so you only need log of bigo.

Define global constants K, N, and N1 through N7. K is constant complexity
all others are free variables.

Then complexities are regular D expressions e.g BigO(N^2 * log(N)).

On a the phone sry typos.