Complexity nomenclature

[H. S. Teoh via Digitalmars-d]

On Fri, Dec 04, 2015 at 08:03:17PM +0000, Andrei Alexandrescu via Digitalmars-d wrote:
> I'll get back to this (on the phone) but this is incorrect:
> 
> sqrt really belongs under poly, as far as asymptotic behaviour is
> concerned.

OK, I guess by poly you mean n^k for k>1.  I was lumping everything
under polynomial for k>0. The reason is because of the homogeneity for
all values of k>0 when it comes to the algebra of complexities.
Obviously, for performance-measuring purposes, k=1 is a significant
landmark.


> Fractional powers are sublinear.

Wrong, O(n^(4/3)) is a fractional power, but it's not sublinear.


> And sqrt times sqrt is linear which is important.
[...]

But it's just a special case of the general multiplicative->additive
rule. Everyone knows 1/2 + 1/2 = 1; it doesn't seem to warrant special
treatment above, say, 1/3 + 2/3 = 1, or any of the other endless
identities involving 1.


T

-- 
Meat: euphemism for dead animal. -- Flora