Complexity nomenclature

[BLM768 via Digitalmars-d]

On Saturday, 5 December 2015 at 22:56:23 UTC, H. S. Teoh wrote:
> Multi-term complexities arise from trivial graph algorithms. 
> They are not limited to the use of multiple containers. More 
> precisely, the multiple terms arise because of the structure of 
> the graph (being composed of nodes and edges); what the 
> algorithms add are functions on nodes and edges.

True. I don't expect that very many people would want to specify 
an algorithmic complexity for those operations, though. It seems 
much more rigidly defined than for lists, arrays, etc. The 
question is not really about whether "complex complexities" will 
exist but whether the user has a practical reason to care about 
specifying them.

> Unfortunately, once you have more than a single variable in 
> your functions, the big-O expressions rapidly become 
> inextricably complex, and can no longer map to nice 
> abstractions like the reals + infinities + infinitesimals 
> linear ordering. For example, two graph algorithms may be, 
> respectively, O(V^2 + E) and O(V + E^2); it's difficult to 
> judge based on that which one is "superior".

Well, if one variable is "capped" (or at least expected to be 
"small") it's easy enough to eliminate that term. Beyond that, 
there isn't necessarily a single ordering of big-O expressions, 
but many of them can be ordered relative to a single variable. 
For instance, O(n + m^2) is less complex than O(n^2 + m) with 
respect to n (and vice versa for m). It's trickier when 
expressions are more deeply nested, but if select one term (in 
this case, n), set all the others to be constant (since none of 
them depends on n), and evaluate the resulting expression tree, 
you should get something half-usable. Some simplifying rules may 
be useful. For instance, log(x^2) should approach log(x) as x 
approaches infinity, I think. (My calculus is a bit rusty.)