Complexity nomenclature

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Fri Dec 4 11:23:56 PST 2015


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.




More information about the Digitalmars-d mailing list