Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/04/2015 09:03 PM, Andrei Alexandrescu wrote:
>> >
>> >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.
>

This is probably sensible in the context of std.container.
Note that some containers only give amortized guarantees. E.g. in C++, 
calling push_back n times on a vector that starts out empty is O(n), but 
the worst case for a single push_back is Ω(n).

Another question is how widely applicable BigO should become beyond 
std.container. E.g. some runtime bounds have multiple parameters.