Complexity nomenclature

[H. S. Teoh via Digitalmars-d]

On Sat, Dec 05, 2015 at 09:52:08PM +0000, BLM768 via Digitalmars-d wrote:
> On Saturday, 5 December 2015 at 20:48:16 UTC, Andrei Alexandrescu wrote:
> >On 12/04/2015 10:24 PM, Timon Gehr wrote:
> >In fact I went through the implementation but soon I hit a wall:
> >what's the _relationship_ between the two growths? It may be the sum
> >O(m + n) but also the product O(m * n). So the operator must be
> >encoded as well.
> >
> >Then what do we do with more complex relationships like O((m + n) log
> >n) etc.
> >
> >Then once you get to some reasonable formula, what's the ordering on
> >top of these complexities? Probably difficult.
> >
> >I gave up on this for the time being. Ideas welcome.
> >
> >Andrei
> 
> Well, we could see how CAS libraries handle this kind of stuff (if
> there _is_ one which handles it)...
> 
> Really, though, with the more complex algorithms, you start running
> into the kinds of issues noted in the first reply to this article:
> http://www.perlmonks.org/?node_id=573138
> 
> Besides, is anyone actually going to specify that they need an
> algorithm that is O(log(n) + m^2) or whatever? Or would a function
> just take _two_ algorithms, assert that each is O(log(n)) and O(m^2),
> respectively, and then compose them itself? The complexities depend on
> the types of container anyway, so in general, you should get only
> multi-term big-O notation when you're using multiple containers (or
> Cartesian products of a container with itself or something like that).
> Can't we just make sure one container's insert() and the other
> container's sort() work within a certain complexity?

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.

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".


T

-- 
They say that "guns don't kill people, people kill people." Well I think the gun helps. If you just stood there and yelled BANG, I don't think you'd kill too many people. -- Eddie Izzard, Dressed to Kill