Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/06/2015 08:48 PM, Andrei Alexandrescu wrote:
>> >The next step up the expressiveness scale would be to have a
>> >sum-of-products representation.
>> >
>> >Proof of concept (disclaimer: hacked together in the middle of the
>> >night, and not tested thoroughly):
>> >
>> >http://dpaste.dzfl.pl/d1512905accd
>> >
>> >I think this general approach is probably close to the sweet spot. ...
>> >
> Brilliant! ...

I have noticed another thing. The comparison operator is an 
underapproximation (it sometimes returns NaN when ordering would 
actually be possible).

E.g., O(n·m) ⊆ O(n²+m²), because n·m ≤ n²+m².

Interesting. It would be nice if the final version had a complete 
decision procedure for ⊆.