Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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

1 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:

enter image description here

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.