
Array resize problem
Hi,
I need help with this problem if anyone can help.
Suppose you have an empty array of size $\displaystyle $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 $\displaystyle $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 to this new array. We then ignore the old array and only insert into this new array. Then $\displaystyle $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 $\displaystyle $n$$ elements inserted if we start with $\displaystyle $s=1$$?
Thanks.