Re: Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

On 12/07/2015 09:43 AM, Timon Gehr wrote:

1-2) BigO("1")
3) BigO("count")
4) BigO("distance(first,last)")
5) BigO("ilist.size()")

There's also this:
On 12/06/2015 12:55 AM, Andrei Alexandrescu wrote:
Well you'd need multiple terms if you want to say things like,
"inserting a range into an array is O(array[].walkLength +
r.walkLength)." When you insert a range in a binary search tree, the
complexity would be O(log(array[].walkLength) * r.walkLength).

BigO("array[].walkLength + r.walkLength");
BigO("log(array[].walkLength) * r.walkLength");

These are still expressible without a DSL: 
BigO(Atom("array[].walkLength") + Atom("r.walkLength")) etc.

Somewhat independently of DSL or not: At this point I'm unclear whether 
supporting free variables with arbitrary names is a good thing. The key 
to unleashing the power of BigO is to compute it when combining 
functions, and the names seem to be specific to the function and 
therefore not easy to combine.


Andrei