# Finding the total work of an array list expansion effort

Suppose we are given an array-based list data structure. Suppose that its initial capacity is $$m > 0.$$ When appending an element to the end of the list, if the list is full, we extend its capacity by $$d > 0$$ array components, copy the old content, and finally append the element. Suppose we are to append $$n \geq m$$ elements to the list. My claim is that the total work is: $$C(n, m, d) = \overbrace{\sum_{k = 0}^{\big\lceil \frac{n - m}{d} \big\rceil}(kd + m)}^{A} - \overbrace{\Bigg( m + \Bigg\lceil \frac{n - m}{d} \Bigg\rceil d - n \Bigg)}^{R}.$$

Above, $$A$$ is the total work of expanding and filling (entirely) the array sufficiently many times in order to accommodate $$n$$ elements, and $$R$$ denotes the number of elements we could have put before expanding once again.

Now, I need to prove it using induction on $$n$$, yet I have no clue how to deal with it. Any help?

• Can you write a recurrence relation for $C(n,m,d)$ in terms of $C(n',m,d)$ where $n'<n$? That would be a good starting point.
– D.W.
Feb 14 at 5:48
• @D.W. Nice one. Thanks! I think I am almost there. Feb 14 at 7:28
• @D.W. I think I proved it using your hint. Could you find some time to review my solution? Feb 15 at 6:46
• @D.W. Also, I am not convinced of rigor of the proof of Lemma 1. Feb 15 at 6:56