# Array resize problem

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.

-
does inserting the new element in the copy of our new array counts as an operation too? – kaharas Mar 12 '13 at 18:57
No, all inserts don't count as a move, only for each element you move from one array to the other array count as a move. – omega Mar 12 '13 at 18:58
Why are you creating the new size as 1+s+⌈log₂s⌉? That doesn't look very efficient. Usually it is created as 2s, in that way the complexity is constant over the long run: O(1) – Tobia Mar 12 '13 at 19:00
True, but I am trying to determine what the moves are with this formula, nevertheless. – omega Mar 12 '13 at 19:03
If this is an exercise problem, it would help if you share what your thoughts are on how to approach it and what you have already tried. – Rahul Mar 12 '13 at 19:04

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)$

-
Does this mean that the big O of the number of moves plus the number of inserts for n inserts is O(nlogn)? – omega Mar 12 '13 at 21:29
No, I looked at the data again. I'm pretty sure it's O(n²) – Tobia Mar 12 '13 at 22:38
You got a different fit but the graph didn't change at all? – Rahul Mar 13 '13 at 4:44
My apologies, I could have sworn I had updated it. In any case it's almost identical to my eyes. – Tobia Mar 13 '13 at 18:50