Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

Timon Gehr <timon.gehr at gmx.ch> wrote:
> On 12/04/2015 07:37 PM, Andrei Alexandrescu wrote:
>> Following up on this, I thought I'd define a little algebra ....
>> It will be closed (no arbitrary expressions)
>> ...
> 
> I think that the exponents matter. E.g. n^1.5 vs n^2.
> The algebra can be made more expressive while simplifying its 
> implementation.
> 
>> 
>> 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)
> 
> Example alternative:
> 
> struct BigO{
>     Fraction logExp;
>     Fraction polyExp;
>     Fraction expBase;
> 
>     bool opCmp(BigO rhs){
>         return 
> tuple(expBase,polyExp,logExp).opCmp(tuple(rhs.expBase,polyExp,logExp));
>     }
>     BigO opBinary(string op:"*")(BigO rhs){
>         return 
> BigO(logExp+rhs.logExp,polyExp+rhs.polyExp,expBase*rhs.expBase);
>     }
>     // ...
> }
> 
> Your cases then become:
> 
> O(1):     expBase=1, polyExp=0, logExp=0;
> O(log n): expBase=1, polyExp=0, logExp=1;
> O((log n)^k): expBase=1, polyExp=0, logExp=k;
> O(sqrt n): expBase=1, polyExp=Fraction(1,2), logExp=0;
> O(n): expBase=1, polyExp=1, logExp=0;
> O(n * log n): expBase=1, polyExp=1, logExp=1;
> O(n * (log n)^k): expBase=1, polyExp=1, logExp=k;
> O(n^k): expBase=1, polyExp=k, logExp=0;
> O(2^n): expBase=2, polyExp=0, logExp=0;
> 
> Combinations just work, especially n^(1/2) * log n.
> 
> 
> 

Nice, I'll continue with this. Thanks! I won't use expBase because no
operation leads to it; instead I'll just lump everything superpoly into one
"fast growing" category.