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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Feb 14 at 5:48
  • $\begingroup$ @D.W. Nice one. Thanks! I think I am almost there. $\endgroup$
    – coderodde
    Feb 14 at 7:28
  • $\begingroup$ @D.W. I think I proved it using your hint. Could you find some time to review my solution? $\endgroup$
    – coderodde
    Feb 15 at 6:46
  • $\begingroup$ @D.W. Also, I am not convinced of rigor of the proof of Lemma 1. $\endgroup$
    – coderodde
    Feb 15 at 6:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.