Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/07/2015 02:07 AM, Andrei Alexandrescu wrote:
> On 12/06/2015 07:50 PM, Timon Gehr wrote:
>> 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 ⊆.
>
> I think it's okay to leave N^^2 + N1 and N + N1^^2 unordered. -- Andrei

Yes, certainly. By complete, I mean it orders everything that can be 
ordered.