1
$\begingroup$

If you have an array that expands when it is completely filled and the new size is N = N + 1 + ceiling(log2(N)) (N is the current size, and then N becomes the new size) (log2 is log base 2).

How can you do an amortized analysis for this? It is confusing because the size of the expansion of the array increases as N increases.

Improve this question
$\endgroup$
1
  • $\begingroup$ Please wait for an answer to your former question, and digest that, before asking another, practically identical one. $\endgroup$
    – Raphael ♦
    Mar 11, 2013 at 7:36

1 Answer 1

Reset to default
1
$\begingroup$

This looks like a homework problem, so I will try to highlight the skeleton of the proof.

  1. The cost of inserting and taking an element out of an array is 1
  2. The cost of resizing an array is equal to the number of elements moved to the new/bigger array.
  3. As a simple case, consider you increase the size of array by 1. Calculate the total cost of resizing?

Repeat the above analysis by doubling the size of array and check which one is better i.e. doubling the size OR increasing by 1? Calculate the amortized cost for both cases? Then you should be good to answer your own question...

Improve this answer
$\endgroup$
2
  • $\begingroup$ The problem I don't understand is, using the accounting method from here ocw.mit.edu/courses/electrical-engineering-and-computer-science/…, to copy elements from one array to another, don't you need money in the bank? When you double the size, you will be able to repay the elements that were previously copied by the time of the next expansion. But with the expansion formula in the above question, the expansion size is too small... $\endgroup$
    – omega
    Mar 11, 2013 at 14:29
  • $\begingroup$ to store $ in time for the next expansion. $\endgroup$
    – omega
    Mar 11, 2013 at 14:29

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