log(n) amortized growth for containers

Jimmy Cao via Digitalmars-d digitalmars-d at puremagic.com
Sun Dec 13 15:59:57 PST 2015


On Friday, 11 December 2015 at 03:55:27 UTC, Andrei Alexandrescu 
wrote:
> To figure a growth schedule that leads to log(n) work per 
> element, a differential equation must be solved:
>
> s(n) / s'(n) = log(x)
>
> where s(n) will be the (continuous extension of the) growth 
> schedule's sum, i.e. s(n) = f(1) + f(2) + ... + f(n). In other 
> word, s(n) is how many elements we moved around, and s'(n) is 
> the capacity after n steps. The division gives us how much work 
> was done per element.
>
> To verify, if s(n) = n, you get O(n) work per element, i.e. 
> quadratic behavior for linear capacity growth. If s(n) = 2^n, 
> you get O(1) work per element.
>
> So I entered the equation above in Wolfram:
>
> https://www.wolframalpha.com/input/?i=y%28x%29+%2F+y%27%28x%29+%3D+log%28x%29

I like this approach to amortized analysis.  I have a question, 
though,

the diff eq you have is

s(n) / s'(n) = log(x)

But the WolframAlpha query solves for effectively:

s(n) / s'(n) = log(n)

Why does x = n?

Shouldn't x be s'(n), so that s(n)/s'(n), how much work was done 
per element, is bounded by the number of elements appended (that 
is about the capacity s'(n))?  I thought number of elements != n, 
but rather something between s'(n) and s'(n-1)?



More information about the Digitalmars-d mailing list