# Amortized cost depending on the number of operations

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?

• 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. Jul 21, 2021 at 8:45
• @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? Jul 21, 2021 at 8:52