Question 3 [15 Marks]
We implemented Dynamic Arrays in class by using an expansion factor of 2. We then reasoned about
the cost of a sequence of Insert operations on such arrays through amortized analysis. In this
question, you will analyse two more strategies for changing the size of Dynamic Arrays and reason
about their sequence performance.
(a) Assume that you start with an empty array of allocated size 10 and expand it by adding 10 (i.e.
new capacity = old capacity + 10) each time it reaches full capacity. You then copy the elements
to the new, expanded array. If the cost is still $1 per array access, and you use the accounting
method to charge each Insert operation $5, will the array ever go into debt? If so, determine
after how many Insert operations. If not, prove by induction that it never runs out of money.
HINT: what is the actual cost of copying each element?
(b) Assume now that you start with an empty array of allocated size c, where c is a constant positive
integer. Each time the array reaches full capacity, you expand its size by adding c slots and
copying over. Starting with a $3 charge per Insert (again, using the accounting method),
suppose that that the charge for an Insert is increased by $2 each time the array grows. The
actual cost remains the same as stated in part (a). So after the first c calls to Insert, the charge
becomes $5, and after 2c Inserts, the charge becomes 7, etc. Will the array ever go into debt?
If so, determine after how many Insert operations. If not, prove by induction that it never
runs out of money.
(c) Using the aggregate approach, compute the amortized complexity of Insert on the array from
part (b) for a sequence of m Insert operations performed on an initially empty array. The
initial allocated capacity as well as the capacity increments should be expressed in terms c, where
c is a constant positive integer. Express your answer in terms of big Θ. HINT: write down the
costs per block of Insert operations and you will see that a pattern emerges.
(d) Performance-wise, how does this expansion strategy (i.e. addition) compare to the array doubling
we saw in class?
(e) Lastly, assume that we implement a Delete operation for Dynamic Arrays. Now consider the
following expansion/shrinking strategy: when the array is full, create an array with double the
size and copy the elements over. When the array is 1/4 full, create a new array with 1/2 of the
size and copy all the elements to the new array. If you charge $3 per Insert and $3 per Delete
using the accounting method, will an array with this expansion/shrinking strategy ever go into
debt? To simplify the calculations, you can assume that the cost per Insert and per Delete
is $1 and that the cost of copying is an additional $1 (if we go by the number of list accesses,
the cost of copying would be $2 – but you do not need to worry about that in this part).
1