Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/04/2015 11:57 PM, Andrei Alexandrescu wrote:
> On 12/04/2015 04:40 PM, Timon Gehr wrote:
>> Another question is how widely applicable BigO should become beyond
>> std.container.
>
> I'm thinking we could add complexity annotations to range functions. For
> example the complexity of map is linear etc.
> ...

It depends on the mapped function.

>> E.g. some runtime bounds have multiple parameters.
>
> Yah, I was wondering how necessary that'd be. One problem is how to
> align parameters of different algorithms, for example say one is n * m
> and the other is m log n. What if they swap the order of m and n?
>
> I guess some reasonable convention should take care of this. Otherwise,
> we'll need to use a hashtable mapping names to (exp, logExp) tuples.
>
>
> Andrei
>

If only products should be expressible, this would maybe be reasonable 
as well:

void foo(@(BigO.linear) int n,@(BigO.linear) int m);

But UDAs for parameters are not supported.