Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

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