Consider an implementation of an extendable array but instea

Consider an implementation of an extendable array, but instead of copying the elements of the array list into an array of double the size (that is, from N to 2N) when its capacity is reached, we copy the elements into an array with [N/2] additional cells, going from capacity N to N + [N/2]. Show that performing a sequence of n push operations (that is, insertions at the end) still runs in O(n) in this case.

Solution

Since number of elements will be N then only this operation will be performed, so total insertions that takes place are N.The size of new array will not matter in this case. So this will take O(n).