Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/07/2015 05:15 PM, Andrei Alexandrescu wrote:
> On 12/07/2015 09:43 AM, Timon Gehr wrote:
>>
>> 1-2) BigO("1")
>> 3) BigO("count")
>> 4) BigO("distance(first,last)")
>> 5) BigO("ilist.size()")
>>
>> There's also this:
>> On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
>>> 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).
>>
>> BigO("array[].walkLength + r.walkLength");
>> BigO("log(array[].walkLength) * r.walkLength");
>
> These are still expressible without a DSL:
> BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc.
> ...

This just goes from one string to two strings and adds some noise on top 
of it. Also, now, what is D and what is in a string is arbitrary.

BigO(Var.array[].walkLength + Var.r.walkLength);

> Somewhat independently of DSL or not:

Yes, notation does not matter at this stage.

> At this point I'm unclear whether
> supporting free variables with arbitrary names is a good thing.

Restricting the set of names to 8 predefined ones does not simplify 
anything. It just means that a mapping of predefined names to real names 
has to be carefully managed manually and clashes have to be avoided, all 
while limiting the value of BigO as documentation.

> The key
> to unleashing the power of BigO is to compute it when combining
> functions, and the names seem to be specific to the function and
> therefore not easy to combine.
> ...

Just substitute something else for those names to get rid of them. That 
is how passing of parameters is handled. Probably we should get some 
actual examples where combination should work to see what could be done.

If you have:

void foo(int n,int m) @BigO("n*m^2"){ ... }

Something like this is easy to implement:

// compute runtime bound from bounds on parameters:
// first expression passed is O(x^3) and second expression passed
// is O(log(y)^(1/2)).
enum bound = getRuntimeBound!foo(BigO("x^3"),BigO("log(y)^(1/2)"));
static assert(bound == BigO("x^3*log(y)"));

Note how the end user does not need to worry much about names.