Amortized Analysis: Suppose we have an implementation of dynamic

array. The array$$s initial size is $0.$ New elements are always appended to the

back of the array. If the array is full, we create a new array with twice of the size

of the current array and copy old elements to the new array. The old array is

$1$

discarded. Use amortized analysis to show that the average cost of performing

each insertion operation is O$(1)$