Array resize problem

Question

I need help with this problem if anyone can help.

Suppose you have an empty array of size $s$. Then you keep inserting elements in it. But before you insert an element, if the array is filled, then you create a new array of size $1+s+\left\lceil\log_2{s}\right\rceil$. You then move every element from the array to this new array (1 move operation per element). Then insert your element in the new array (we ignore the old array and only insert to this new array). Then $s$ becomes the size of this new array.

How many move operations (an insert doesn't count as a move) are done in total for $n$ elements inserted if we start with $s=1$?

Thanks.

Answer 1

Approaching the problem numerically, I wrote a small Python program to compute the sizes and moves:

size = 1
moves = 0
while size <= 1000000:
    moves += size
    log_2_size = int(ceil(log(size, 2)))
    size = 1 + size + log_2_size
    print size, moves

Then I plotted the couples of sizes and moves $(x,y)$ in a chart and tried various functions to see which one fit the growth.

Apparently the power function ($y=ax^p$) is a good fit for this data series. From a rough visual estimate, I got the coefficient $a=0.0484$ and $p=1.95$

Here's the updated chart:

I think it's safe to say that the magnitude of the number of moves plus the number of inserts for $n$ inserts is $O(n^2)$