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