Data-structures 3

Dynamic array

\begin{matrix} This array doubles in size each time an insertion is made but the array is full \\ Resizing is an O (n) operation as it requires copying all elements \\ Let Φ (D_{i}) = 2 n_{i} - l_{i} \\ Let P (n_{i}) = c_{i} + (Φ (D_{i}) - Φ (D_{i - 1})) \\ \sum_{i = 1}^{n} P (n_{i}) = \sum_{i = 1}^{n} c_{i} + Φ (D_{n}) - Φ (D_{0}) = \\ = n + (2 n - n) - (0 - k) = 2 n + k \sim 2 n \\ ⟹ Amortized complexity is O (\frac{2 n}{n}) = O (1) \end{matrix}