Dynamic Arrays: Implementation and Amortized Analysis

1. The Problem with Static Arrays and the Dynamic Solution

A standard array is a contiguous block of memory. This is great for fast access—retrieving an element at a given index is an O(1) operation. However, its fixed size is a significant drawback. If you need more space than you initially allocated, you're out of luck.

A dynamic array is an abstraction built on top of a static array. It provides the illusion of an array that can grow or shrink on demand. Many languages provide this out of the box: ArrayList in Java, std::vector in C++, and lists in Python are all examples of dynamic arrays.

Internally, a dynamic array manages:

• A pointer to a static (fixed-size) array.
• A size variable: the number of elements currently stored.
• A capacity variable: the total number of slots available in the underlying static array.

When you add an element (append or push_back), if size < capacity, the operation is simple: place the new element at the next available spot and increment size. This is O(1). The challenge arises when size == capacity. At this point, the array must be resized.

2. The Resizing Strategy: Why Doubling is Smart

How should we resize? A naive approach might be to add a fixed number of new slots (e.g., 10) each time we run out of space. This turns out to be very inefficient. As the array gets large, you'll be performing this expensive resizing operation more and more frequently.

A much better approach is to resize by a multiplicative factor. The standard strategy is to double the capacity every time the array becomes full. Let's explore the intuition behind why this is so effective.

As the video shows, when you insert N elements, most insertions are fast O(1) operations. Only a few—those that trigger a resize—are slow O(k) operations, where k is the number of elements to copy. How do we describe the complexity of a single append operation that is sometimes O(1) and sometimes O(N)? This brings us to amortized analysis.

3. Amortized Time Complexity: Averaging Out the Cost

The worst-case complexity of an append operation is indeed O(N), because in the worst case, you have to copy all N elements to a new array. However, this worst case happens so rarely that saying the operation is O(N) is overly pessimistic and doesn't reflect its excellent average performance.

Amortized analysis gives us a way to calculate the average cost per operation over a sequence of operations in the worst case. It smooths out the expensive "peaks" across the many cheap operations.

To formalize this, let's explore the Aggregate Method of amortized analysis.

Let's quickly summarize the math from the article. For a sequence of n appends:

• The cost of simple insertions is 1 unit each. Total cost = n.
• The cost of resizing happens at insertions i = 1, 2, 4, 8, ... , 2^k where 2^k < n. The cost of each resize is i.
• The total cost T(n) is the sum of simple insertion costs plus the sum of resizing costs:
  $T(n)=n+{\sum }_{j=0}^{\lfloor {\log }_2(n-1)\rfloor }{2}^j$
• The geometric series 1 + 2 + 4 + ... + 2^k sums to 2^(k+1) - 1, which is less than 2n.
• So, the total cost T(n) < n + 2n = 3n. This is O(n).
• The amortized cost per operation is the total cost divided by the number of operations: T(n) / n < 3n / n = 3.
• Therefore, the amortized time complexity of appending to a dynamic array is O(1).

4. Implementing a Dynamic Array

Now that we've covered the theory, let's see how this is implemented in practice. The following video provides a clear, step-by-step walkthrough of creating a DynamicArray class.

For a different perspective, especially one that makes memory management explicit, you can look at a C implementation. You don't need to study this in detail, but glancing at the vector_double_capacity function in the resource "Data Structures Dynamic Array in C" (LINK) can reinforce what's happening under the hood when a language doesn't manage memory for you. The logic is identical: allocate new memory (of double the size), copy old elements, and free the old memory.

5. Shrinking the Array

We've focused on growing, but dynamic arrays should also shrink to save space when elements are removed. A naive strategy would be to halve the capacity when size becomes capacity / 2. This, however, can lead to a performance problem called thrashing.

Imagine an array is full (size == capacity). A push_back doubles the capacity. Now, size is just over half the new capacity. If you immediately pop_back, the size becomes half the capacity, triggering a shrink. If you then push_back again, it triggers a grow. A rapid sequence of pushes and pops around this boundary would cause repeated, expensive resizes.

A common, robust strategy is to halve the capacity only when the size drops to one-quarter of the capacity (size <= capacity / 4). This provides a buffer that prevents thrashing. The amortized analysis for this also works out to O(1).

Conclusion

Congratulations! You've successfully implemented and analyzed your first major data structure. This lesson not only introduced the dynamic array but also equipped you with the powerful concept of amortized analysis, a vital tool for any software architect.

Key Takeaways:

• Dynamic arrays provide a flexible, resizable interface built on top of fixed-size static arrays.
• The key operation is resizing. Using a multiplicative growth factor (like doubling) is far more efficient than an additive one.
• An append operation has a worst-case time complexity of O(N) but an amortized time complexity of O(1).
• Amortized analysis calculates the average cost per operation over a worst-case sequence, providing a more realistic performance measure for data structures with occasional expensive operations.
• Shrinking strategies must be designed carefully to avoid "thrashing."

Next Steps

We've explored a data structure that excels at O(1) access and O(1) amortized appends. But what about inserting or deleting from the middle of the sequence? This is an O(N) operation for a dynamic array. In our next lesson, we will investigate the linked list, a data structure with a fundamentally different set of performance trade-offs that address this very problem.