Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/07/2015 02:05 AM, Andrei Alexandrescu wrote:
> 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!
> ...

Even better: I was wrong when I claimed it does not work.
For 0<=x, it actually works as-is:

O((f+g)^x) = O(max(f,g)^x) = O(max(f^x,g^x)) = O(f^x+g^x).

>>> 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.
> ...

Well, how?

> 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?

There is no priority. The parser explicitly rejects log n^x. :-)

> Why is power ^ in this notation and ^^ in D?

Because ^ is taken for bitwise xor in D due to backwards-compatibility 
constraints.

> All these differences without a distinction are gratuitous.
> Just use D.
> ...

D does not allow overloading of syntax to the extent necessary to make 
similar things really pleasant in the long run, and it has been 
repeatedly argued that this is a good thing; that custom parsing should 
be used instead. It is easy to align the parser with D syntax. Anyway, 
syntax is not the problem here, and the implementation can be downgraded 
to not support parsing and/or proper names at any point.