Amortized Analysis

Solution

The total cost of a sequence of operations divided by the number of operations in the sequence.

For the rest of this section, consider a DynamicArray data structure, which stores int values in an internal array arr and tracks how many are in use with size. When add finds the internal array full, it calls grow, which allocates a bigger array, copies the size elements into it, and makes it the new arr. Let $n$ be the number of elements stored.

Solution

Every add after the first finds the array full. The 2nd add copies $1$ element, the 3rd copies $2$ , and so on up to the $n$th, which copies $n - 1$ :

1 + 2 + \dots + (n - 1) = \frac{n ( n - 1 )}{2} \in O (n^{2})

Dividing $O (n^{2})$ of total work by $n$ adds gives $O (n)$ amortized per add.

Solution

A grow happens when the array holds $1$ , $2$ , $4$ , …, $n /2$ elements, and copies that many:

1 + 2 + 4 + \dots + n /2 = n - 1 \in O (n)

Dividing $O (n)$ of total work by $n$ adds gives $O (1)$ amortized per add.

Solution

A factor of $3$ still gives $O (1)$ amortized: any factor greater than $1$ makes the number of grow calls logarithmic in $n$ , so the total copying is a geometric series, which is $O (n)$ . Growing by $100$ slots gives $O (n)$ amortized, the same as growing by one slot: grow runs every $100$th add, so the number of grow calls is $n /100$ , still linear in $n$ , and each copies up to $n$ elements, so the total is $O (n^{2})$ .

Solution

Average case averages over a distribution of inputs and needs an assumption about which inputs are likely. Amortized averages over a sequence of operations and assumes nothing about probability. The $O (1)$ bound on add holds for any sequence of $n$ adds, so it is amortized.

Solution

SortedArray.add is $O (n)$ amortized. Starting from an empty array of fixed initial capacity, the copying in grow is the same as for DynamicArray: $O (n)$ copies over $n$ calls. The shifting is the problem. Add $n$ values in descending order. Every new value belongs at index $0$ , so the $k$th call shifts all $k - 1$ elements already stored:

0 + 1 + 2 + \dots + (n - 1) = \frac{n ( n - 1 )}{2} \in O (n^{2})

The total is $O (n) + O (n^{2}) = O (n^{2})$ , and dividing by $n$ calls gives $O (n)$ amortized per call. This matches the worst-case bound for a single call. Amortized analysis does not have to give a better bound: it measures the cost per operation over a worst-case sequence. Doubling spreads the cost of growing over enough adds to give $O (1)$ amortized growth cost. But in this descending-order sequence, every add shifts all the elements already stored, so the shifting still costs $O (n)$ amortized per add.