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
