20250319_D&A

Amortized Analysis

Feedback

The strategy for arbitrary inserting and removing sequence is incorrect. Consider the following scenario:
The current size of the array is $2 n$ and it contains $n$ elements. Now, I remove the last element. According to your algorithm, the array shrinks and costs $O (n)$ time. Now the array is of length $n$ and has $n - 1$ elements. Then I insert two elements to the end. You have to double the length of the array again, costing another $O (n)$ time. Then I keep removing two elements, inserting two elements, ... Your strategy takes time $O (n)$ every two operations.

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.

informal first draft:

a)
Since we also also did it like this in the exercise lesson, I've chosen to double the array each time it is resized. Therefore

k = 2 n

costs:

insertion: $O (1)$
insertion with resizing (happens every $\frac{1}{n}$ time):
1. resizing the array from $n$ to $2 n$ takes $O (n)$ time
2. inserting the new element takes $O (1)$ time
3. total: $O (n + 1) = O (n)$

Therefore, for inserting $n$ elements:

O (\underset{inserting every time}{\underset{⏟}{n \cdot 1}} + \underset{resizing every 1/n time}{\underset{⏟}{\frac{1}{n} \cdot n}}) = O (n + 1) = O (n)

b)
Shrinking
We could shrink a vector when more than half of it is empty.

costs:

deletion: $O (1)$
deletion with resizing (happens every $\frac{1}{n}$ time):
1. resizing the array from $2 n$ to $n$ takes $O (n)$ time
2. deleting the element takes $O (n)$ time
3. total: $O (n + 1) = O (n)$

Therefore, for removing $n$ elements:

O (\underset{removing every time}{\underset{⏟}{n \cdot 1}} + \underset{resizing every 1/n time}{\underset{⏟}{\frac{1}{n} \cdot n}}) = O (n + 1) = O (n)

And insertion and deletion together take

\underset{insertion}{\underset{⏟}{O (n)}} + \underset{deletion}{\underset{⏟}{O (n)}} = O (2 n) = O (n)