Question

Consider a smart array that automatically expands on demand. (Like the java.util.ArrayList.) It starts with some given initial capacity of 100, and whenever it expands, it adds 50 to the current capacity. So, for example, at the 101st add, it expands to a capacity of 150. How many total units of work would be needed to add 1000 items to this smart array? Assume it takes one unit of work to write an item into an array location, and one unit of work to allocate a new array.

Answer 1

Total unit of work required is 1019 units.

Solution:

As per the question:

Initial capacity = 100

On each expansion 50 is added to the present capacity.

Now,

Work done required in addition of 1000 items = 1000 unit

No. of times there is a need for the allocation of a new Array is given by:

`n = (1000 - 100)/(50) = 18`

We know that:

On addition of 101th element it expands from 100 to 150

On addition of 151st element it expands from 150 to 200 and so on till

On addition of 951st element it expands from 950 to 1000

Now,

For an array of 100 size - 1 for initial allocation.

Therefore, total work done is given by:

W =
`1000 + (1000 - 100)/(50) + 1 = 1019\ units`