Complexity nomenclature

[BLM768 via Digitalmars-d]

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?