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?

  • $\begingroup$ The runtime is always with respect to the size of the input. The output doesn't have to be the same length, and the run-time is not calculated with respect to it. $\endgroup$
    – nir shahar
    Jul 21, 2021 at 8:45
  • $\begingroup$ @nirshahar If I understand correectly the run-time should depend only on $n$ here, but $m$ can be $\theta(n^2)$ or $\theta(n^3)$ for example, so this gives two different answers. otherwise how can we settle this? $\endgroup$ Jul 21, 2021 at 8:52


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.

Browse other questions tagged or ask your own question.