Considering a dynamic array that grows by a constant factor $k$ (the new array has $k$ more cells than the last one) each time the array is full which initially has $n$ elements in it. Calculating the amortized time for insertion:
Consider a sequence $m$ worst case insert operations, then we have constant time for each insertion to a table which sums to $\Theta(m)$ and number of copied items is $(n+1) + (n+1+k) + (n+1+2k) + \dots + (n+m) = m(n+1) + (k + 2k + 3k + \dots + (m-1))= m(n+1) + \frac{(m-k)(k+m)}{2}= m(n+1)+\frac{ m^2 - k^2}{2}$
So in total the runtime of the sequence is:
$\Theta(m) + \Theta(m(n+1) + \frac{m^2-k^2}{2}) = \Theta(m) + \Theta(m(n+1) + m^2) = \Theta(m(n+m))$
Hence the amortized time is $\Theta(n+m)$
The problem is the question states "calculate the amortized time assuming $n$ is the number of elements in the array" so it is confusing, can I treat it as $\Theta(n)$ because we now have $m+n$ elements in the array? this seems like what they mean but now $n$ is the number of elements before the sequence and also the number of elements after the sequence. How should we explain this runtime?
