Complexity nomenclature

[Timon Gehr via Digitalmars-d]

On 12/06/2015 08:59 AM, Ola Fosheim Grøstad wrote:
> On Sunday, 6 December 2015 at 03:24:24 UTC, Timon Gehr wrote:
>> Some upper bounds are incomparable, so there would not be a total
>> order. But that is not a problem.
>
> It is a problem in all cases as you usually dont have an optimal bound.

Are you complaining that the given implementation does not support 
'min', or what are you trying to say here?

> And with your approach that will most certainly be guaranteed to happen.

How is that specific to my approach? I only showed a more expressive 
BigO implementation.

> Comparing bounds does not mean you are comparing running time.
> ...

BigO represents a set of functions. Comparing BigO checks for subset 
inclusion.

> O(1) implies O(f(x)), O(N) implies O(N^2).
>

For our purposes, O(f) = { g | ∃c. ∀x⃗. |g(x⃗)| ≤ c·|f(x⃗)|+c }.

O(1) ⊆ O(f(x)), O(N) ⊆ O(N²).

<= checks ⊆.
== checks =.

(The final implementation should use exact fractions instead of doubles.)

> You can also get tighter bounds for specific input models.
>

Yes, you can.