Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

On 12/04/2015 11:06 AM, Andrei Alexandrescu wrote:
> On 12/04/2015 01:05 AM, Tofu Ninja wrote:
>> Also maybe a simpler idea would just be to annotate the the operations
>> with there complexity with UDAs. That way things that really care about
>> the complexity can get it, and those who don't can ignore it. It has the
>> benefit of being self documenting as well.
>
> Well look at what the cat dragged in:
>
> http://dpaste.dzfl.pl/711aecacc450

Following up on this, I thought I'd define a little algebra for 
complexities. It will be closed (no arbitrary expressions) and will 
support only the usually encountered complexities.

The idea is to allow functions to compute their own complexity in terms 
of complexities of their respective primitives.

Here's the algebra.

Terms:

1 = O(1)
log = O(log n)
plog = O((log n)^k)
sqrt = O(sqrt n)
lin = O(n)
linlog = O(n * log n)
linplog = O(n * (log n)^k)
poly = O(n^k)
exp = O(2^n)

Ordering:

Terms above are in increasing order.

Summation:

x + y = max(x, y)

Product:

        | 1       log      plog     sqrt  lin      linlog   poly  exp 

-------+------------------------------------------------------------
1      | 1       log      plog     sqrt  lin      linlog   poly  exp 

log    | log     plog     plog     ?     linlog   ?        poly  exp
plog   | plog    plog     plog     ?     linplog  linplog  poly  exp
sqrt   | sqrt    ?        ?        lin   poly     poly     poly  exp
lin    | lin     linlog   linplog  poly  poly     poly     poly  exp
linlog | linlog  linplog  linplog  poly  poly     poly     poly  exp
poly   | poly    poly     poly     poly  poly     poly     poly  exp
exp    | exp     exp      exp      exp   exp      exp      exp   exp

I've left a few question marks for the tricky cases. Ideas?


Andrei