log(n) amortized growth for containers

[Andrei Alexandrescu via Digitalmars-d]

On 12/11/15 9:02 PM, Timon Gehr wrote:
> 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.

How do you prove that? -- Andrei