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.
