20250319_D&A

Amortized Analysis

1) inserting

We assume that inserting and copying elements between arrays takes $O (1)$ time.

We will choose $n = 2^{k}$ , doubling the array size every time the array is full.

Now, when there is space in the array, insertion takes $O (1)$ time. When the array is full, however, it grows from $2^{i}$ to $2^{i + 1}$ elements and requires copying $2^{i}$ elements.

e.g. when we start with an array of size $1$ , the array doubles

1, 2, 4, 8, \dots, 2^{k - 1}

This is a geometric series, and the copy costs are

\sum_{i = 0}^{k - 1} 2^{i} = \frac{1 (2^{k} - 1)}{2 - 1} = 2^{k} - 1 \overset{def. n}{=} n - 1

Thus, the copying of $n$ elements takes $O (n)$ time and the insertion of $n$ elements takes amortized $O (n)$ time, which translates to

\frac{O (n)}{n} = O (1)

amortized constant time per insertion.

2) removing

We assume that removing elements also takes $O (1)$ time.

We can choose to halve the size of the array (which still has $n = 2^{k}$ length) every time the number of elements frops below $\frac{1}{2}$ of the array's size.

Suppose we start with an array of size $2^{i}$ , and the number of elements falls from $2^{i}$ to $2^{i - 1}$ . In this case, we shrink the array and copy $2^{i - 1}$ elements to the new array.

Thus, we come to a total number of copy operations of

\sum_{i = 0}^{k - 1} 2^{i} = \dots = n - 1

Equivalent to the argumentation for copying and inserting elements, copying and removing $n$ elements also takes amortized $O (n)$ time, i.e. constant time per element.

inserting + removing
Since inserting and element takes $O (1)$ and deleting also takes $O (1)$ , inserting + removing also takes amortized $O (1 + 1) = O (1)$ constant time.