log(n) amortized growth for containers

[Timon Gehr via Digitalmars-d]

On 12/11/2015 04:55 AM, Andrei Alexandrescu wrote:
>
> Here's a quick thought on growth schedule for arrays. The classic
> approach is to grow by a geometric schedule. For example: 1, 2, 4, 8,
> 16, etc. That way, n memory moves are necessary for achieving a capacity
> equal to n, so on average we spend a constant amount of time per
> appended element.
>
> The main disadvantage with this growth schedule is there are on average
> n/2 slack memory slots. Also, a growth factor of 2 is unfriendly to the
> memory allocator (long discussion) so a smaller one (such as the golden
> cut or less) would be better.
>
> Anyhow, I was thinking why O(1) amortized growth and not O(log n)? The
> latter is considered scalable all right and the hope is to get a
> corresponding reduction in the slack memory space. ...


E.g. the following sequence of capacities leads to amortized Θ(log n).

c(0) = 0, c(k+1) = c(k)+c(k)/⌊log₂(c(k)+2)⌋+1.