Amortized Analysis: Dynamic Array Resizing

The Problem: Worst-Case vs. Reality

As you know from your Java experience, an ArrayList provides the convenience of a list that can grow, built on top of a standard array. The challenge arises when the underlying array becomes full. To add a new element, a new, larger array must be allocated, and all existing elements must be copied over.

Let's break down the cost:

• Cheap Operation: If there is space in the array, adding an element is a simple assignment. This is an O(1) operation.
• Expensive Operation: If the array is full, we must copy all n existing elements to a new array. This is an O(n) operation.

So, the worst-case time complexity for a single add operation is O(n). While correct, this is a misleadingly pessimistic view because this expensive O(n) cost is incurred only rarely. Amortized analysis gives us a way to calculate the average cost per operation over a sequence, smoothing out these infrequent, expensive spikes.

Let's begin with a high-level introduction to amortization from MIT OpenCourseWare. This will set the stage for our analysis.

The Aggregate Method: Summing It All Up

The most direct way to perform amortized analysis is the aggregate method. The idea is simple: calculate the total cost for a sequence of N operations and then divide by N to find the average, or amortized, cost per operation.

Let's analyze the strategy used by ArrayList: when the array is full, its capacity is doubled. We'll start with an array of capacity 1 and insert n elements.

The following resource provides a step-by-step calculation for this exact scenario.

As you saw in the reading, the total cost for n insertions is the sum of two parts:

1. Insertion Cost: Each of the n elements must be inserted, which costs n operations in total.
2. Copying Cost: Resizing occurs when the number of elements is a power of two. The total number of elements copied is 1 + 2 + 4 + 8 + ... + 2^k where 2^k < n. This is a geometric series that sums to approximately n-1.

So, the total cost for n insertions is roughly n (for the insertions) + n (for the copying) = 2n.

The amortized cost per operation is then:

Even though some operations are expensive, the average cost levels out to a constant. The image below provides a great visual summary of this calculation for the first 10 operations.

But Why Double?

A crucial question for an SDE interview is why we use a multiplicative growth factor (like doubling) instead of an additive one (e.g., adding 10 new slots each time). Let's explore the consequences of an additive strategy.

As you can see, increasing capacity by a constant amount (+ c) results in a total copy cost of $\Theta (N^2)$ for N insertions. This leads to an amortized cost of $\Theta (N)$, which is far less efficient and defeats the purpose of a dynamic array. The multiplicative growth ensures that the cost of resizing is "paid for" by a sufficiently large number of cheap O(1) insertions.

The Accounting Method: Paying for Growth in Advance

Another, often more intuitive, way to think about this is the accounting method. Imagine each operation carries a "payment" or "amortized cost".

• If the amortized cost is greater than the actual cost, the difference is saved as "credit" in a "bank account".
• If an operation is expensive (like a resize), we can use the credit from the bank account to pay for it.

The key rule is that the bank account balance can never go negative.

For our dynamic array, let's set an amortized cost of 3 units for every add operation.

1. Actual Cost: Inserting the element into its slot costs 1 unit.
2. Credit: The remaining 2 units are saved as credit and associated with the newly inserted element.

Now, consider what happens when the array becomes full. Let's say the capacity is m and we need to double it.

• The array is full, meaning it contains m elements.
• The last time the array was resized was when it grew to size m. At that point, it was half full, containing m/2 elements.
• Therefore, the m/2 elements in the second half of the array were all added since the last resize. Each of them deposited 2 units of credit.
• Total credit available: (m/2) elements * 2 units/element = m units.
• The actual cost of the resize is copying m elements, which costs m units.

The saved credit exactly pays for the expensive copy operation! The 3-unit payment for each insertion successfully covers all future costs, proving that the amortized cost is constant.

The following video provides an excellent walkthrough of this method.

Practical Takeaways for Java

As a Java developer, this directly relates to java.util.ArrayList. The add method has an O(1) amortized time complexity precisely because of this resizing strategy. Knowing this has practical implications:

• If you have a good estimate of how many items you'll store, you can help the ArrayList avoid resizing costs altogether by using the ArrayList(int initialCapacity) constructor.
• Similarly, if you're about to add a large number of elements, calling ensureCapacity(int minCapacity) beforehand can pre-allocate the needed memory in one go, preventing a sequence of costly reallocations.

Conclusion

In this lesson, we demystified the performance of one of the most common data structures by applying amortized analysis.

Here are the key takeaways:

• Amortized analysis calculates the average cost of an operation over a sequence, giving a more practical performance measure than worst-case analysis when expensive operations are rare.
• Adding an element to a dynamic array has an O(n) worst-case complexity but an O(1) amortized complexity.
• This efficiency is achieved by using a multiplicative growth strategy (e.g., doubling capacity). An additive strategy would lead to an inefficient O(n) amortized cost.
• We can formalize this using the aggregate method (summing total costs) or the accounting method (saving credit from cheap operations to pay for expensive ones).

We've now completed our foundational look at complexity. In the next lesson, we will shift gears and begin exploring powerful algorithmic patterns, starting with the two-pointer technique, a clever method for solving a variety of problems on arrays and strings.