log(n) amortized growth for containers

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Thu Dec 10 20:53:46 PST 2015


On 12/10/15 10:55 PM, Andrei Alexandrescu wrote:
>
> So the growth schedule is exponential of the LogIntegral(n). Let's write
> it as:
>
> f(n) = 2^^li(n)

I was wrong here, that's the number of total moves. The growth schedule 
is proportional to the derivative of that:

f(n) = 2^^li(n)/log(n)


Andrei



More information about the Digitalmars-d mailing list