Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

On 12/06/2015 06:21 PM, Timon Gehr wrote:
> The implementation of power on BigO given does not actually work in
> general (there should have been an enforcement that makes sure there is
> only one summand). I'll think about whether and how it can be made to
> work for multiple summands.

No matter, you may always use runtime assertions - after all it's all 
during compilation. That's the beauty of it!

>> 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.
>
> I generally tend to avoid DSLs based solely on operator overloading, as
> they don't always work and hence are awkward to evolve. Here, the
> biggest current nuisance is that the variable names are not very
> descriptive.

The bright side is you get to standardize names. If you limit names to 
K, N, and N1 through N7 then you can always impose to APIs the meaning 
of these.

Another bright side is people don't need to learn a new, juuust slightly 
different grammar for complexity expressions - just use D. For example 
the grammar you defined allows log n without parens - what's the 
priority of log compared to power etc? Why is power ^ in this notation 
and ^^ in D? All these differences without a distinction are gratuitous. 
Just use D.

> If we'll go with a log(BigO) function, we possibly want to
> make BigO closed under log without approximating iterated logarithms:
>
> struct Term{
>      Variable n;
>      Fraction[] exponents; // exponents[0] is exponent of n,
>                            // exponents[1] is exponent of log n,
>                            // exponents[2] is exponent of log log n, ...
> }
>
> Then O(log(f^c*g^d)) = O(log(f)+log(g)) = O(log(f+g)) [1], and hence
> every BigO has a well-defined logarithm.
>
>
> [1] O(log(f+g)) ⊆ O(log(f*g)) = O(log(f)+log(g)).
>      O(log(f)+log(g)) ⊆ O(max(log(f),log(g)))
>                       = O(log(max(f,g)))
>                       ⊆ O(log(f+g)).

Yah, the stuff under log must be restricted. Here's the grammar I'm 
toying with:

Atom ::= K | N | N1 | ... | N7
SimpleExp ::= SimpleTerm ('+' SimpleTerm)*
SimpleTerm ::= SimpleFactor ('*' SimpleFactor)*
SimpleFactor ::= Atom ('^^' double)? | '(' SimpleExp ')'
BigO ::= Term ('+' Term)*
Term ::= SimpleFactor ('*' 'log' '(' SimpleExp ')' ('^^' double)?)?

(I used regex notations for "optional" and "zero or more".)

This is expressible with D's native operations (so no need for custom 
parsing) and covers, I think, what we need. It could be further 
simplified if we move some of the grammar's restrictions to runtime 
(e.g. no need for SimpleXxx, some expressions can be forced to be simple 
during "runtime").


Andrei