Consider a dynamic array with a capacity of and a size of . This means that there are currently elements in the array. We perform the following sequence of operations:
add 5
add 7
add 9
insert 3 1
insert 6 2
Tip: Here, add means that we append an element to the array, insert means that we insert to the array at the -th index (assuming zero-based indexing).
How many total copy operations of array elements will we perform when doing the required operations with the array?
Note that elements are copied in the following cases:
When the array capacity increases, all elements from the old array are copied. In this case, count all individual copy operations performed.
When an element is inserted into a dynamic array at a specific index, all elements from the index of the inserted element to the end of the array are copied one position to the right.
Assume that the scaling factor is .