Consider the append() operation for a Dynamic Array. In the best case, the operation is O(1). This corresponds to the case where there was room in the space we have already allocated for the array. However, in the worst case, this operation slows down to O(n). This corresponds to the case where the allocated space was full and we must copy each element of the array into a new (larger) array. This problem is designed to discover runtime bounds on the average case when various array expansion strategies are used, but first, some information on how to perform an amortized analysis is necessary.

1. Each time an item is added to the array without requiring reallocation, count 1 unit of cost. This cost will cover the assignment which actually puts the item in the array.

2. Each time an item is added and requires reallocation, count X + 1 units of cost, where X is the number of items currently in the array. This cost will cover the X assignments which are necessary to copy the contents of the full array into a new (larger) array, and the additional assignment to put the item which did not fit originally.

To make this more concrete, if the array has 3 spaces and is holding 2 items, adding the third will cost 1. However, if the array has 3 spaces and is holding 3 items currently, adding the 4th item will actually cost 4 (3 to move the existing items + 1 to assign the 4th item once space is available).

Now our goal is to calculate how many units are spent in the entire sequence of N append operations then use it to find the average unit cost for an append. When we can bound an average cost of an operation in this fashion, we call it amortized execution time. Note that this method charges the same amortized execution time to each operation in the sequence of N append operations even though the same operation will experience very different costs across a sequence. It relies on the fact that many of the operations in the sequence contribute little cost and only a few operations contribute a high cost to the overall time.

1. How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 3, assuming that the array will double in capacity each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the amortized big-O complexity for an append?

2. How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 3, assuming that the array will grow by a constant 2 spaces each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the amortized big-O complexity for an append?

will rate thanks :) !