Complexity nomenclature

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Sun Dec 6 07:43:54 PST 2015


On 12/06/2015 03:39 PM, Timon Gehr wrote:
>
> For our purposes, O(f) = { g | ∃c. ∀x⃗. |g(x⃗)| ≤ c·|f(x⃗)|+c }.

Hm, this does not actually work too well. E.g., we want

O(n+m) ⊆ O(n log m + m log n).

This breaks down with that definition if we e.g. fix m=1 and let n vary.

Anyway, I think this can be fixed.


More information about the Digitalmars-d mailing list