I need some help with this problem.
Suppose you have an array of size $n$ where $n = 4^i$ for some $i \geq 0$, with initially $n$ elements in it. Let $m$ be the current number of elements in the array at any point in time.
Then you keep deleting an element from the array one at a time. But right after every delete, if $\frac{m}{n} \leq \frac{1}{8}$ then we create a new array of size $\frac{n}{4}$ and copy the elements (1 copy operation per element) from the previous array to this new array and this is the array that we now delete from (we then ignore the old array and $n$ is now the size of this new array).
What is the total number of copy operations given an array of size $n$?
Thanks.
Judging by your trace, you start with $4^i$ elements, you then copy across $4^i / 8$, then you copy across $4^i / 64$, etc. Essentially you want to find $2 + 8 + 32 + ... + 4^{i}/8$. This is just the geometric series $$2 (1 + 4 + ... + 4^{i-2}) = 2(4^{i-1} - 1)/3$$
So in the case of $n=1024$ initially, $i = 5$, and the number of copy operations is: $$ \frac{2}{3} (4^4 - 1) = 170$$