Complexity nomenclature

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Sat Dec 5 12:48:16 PST 2015


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.

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


Andrei



More information about the Digitalmars-d mailing list