BankingArray

The banking method is sometimes used to calculate the amortized cost of a process. In our system, every time a value is written to memory, it will cost 1 dollar. We are going to use this system to study the behavior of a dynamic array. The array starts empty with some initial capacity. If an item is added to the array, a memory write occurs, and the cost is 1 dollar. If the item added doesn't fit in the array, a new array is allocated which is twice the size of the previous array. All of the elements from the old array must be copied over, costing 1 dollar for each element copied. Then the new item must be added, costing another dollar. For example, if 3 adds occur to an array with initial capacity 1:

Action     Capacity      Size      Cost Incurred
-------------------------------------------------
Start      capacity = 1  size = 0  (empty)
Add        capacity = 1  size = 1  (cost = 1)
Add        Doesn't fit
 -allocate capacity = 2  size = 0  (empty)
 -copy     capacity = 2  size = 1  (cost = 1)
 -add      capacity = 2  size = 2  (cost = 1)
Add        Doesn't fit
 -allocate capacity = 4  size = 0  (empty)
 -copy     capacity = 4  size = 2  (cost = 2)
 -add      capacity = 4  size = 3  (cost = 1)

So the total cost is 1+1+1+2+1 = 6. Given the initial capacity of the empty array, and the number of adds that occur, return the cost.