Amortized Analysis: Aggregate and Accounting Methods

1. The Limits of Single-Operation Worst-Case Analysis

Let's consider a familiar data structure: a dynamic array (like std::vector or ArrayList). It provides an append operation that adds an element to the end.

• The "cheap" case: If the underlying array has space, this is an O(1) operation. You just place the element at the next index.
• The "expensive" case: If the array is full, the data structure must perform a costly resize:
  1. Allocate a new, larger array (typically double the size).
  2. Copy every element from the old array to the new one.
  3. Add the new element.
     This single operation takes O(n) time, where n is the current number of elements.

A strict worst-case analysis would conclude that the append operation is O(n). If we need to perform m appends, does this mean the total time is O(m \cdot n)? This feels incorrect, and it is. The expensive O(n) cost happens only rarely. Amortized analysis provides a formal way to prove that the average cost is, in fact, much lower.

2. The Aggregate Method: A Total Cost Perspective

The aggregate method is the most straightforward approach to amortized analysis. The process is simple:

1. Determine the total worst-case time, $T(n)$, for a sequence of $n$ operations.
2. The amortized cost per operation is then calculated as $T(n)/n$.

Let's apply this to the multi-pop stack example, a classic introductory problem. A stack supports PUSH (cost 1), POP (cost 1), and MULTIPOP(k) (cost k). A naive analysis would say a sequence of n operations could cost O(n^2) if all were MULTIPOP(n). However, this is impossible.

To see how to derive a tighter bound, let's watch a clear explanation.

As the video showed, for any sequence of $n$ operations on an initially empty stack:

• The total number of PUSH operations is at most $n$. Total cost for pushes is O(n).
• An element must be pushed onto the stack before it can be popped.
• Therefore, the total number of items popped (summed across all POP and MULTIPOP calls) cannot exceed the total number of items pushed. This is at most $n$.
• The total cost for all POP and MULTIPOP operations combined is therefore O(n).

So, the total cost for any sequence of $n$ operations is O(n) + O(n) = O(n).
The amortized cost per operation is O(n) / n = O(1).

This is a powerful result: despite some operations being potentially expensive, the average cost over any sequence is constant.

3. The Accounting Method: Pre-paying for Future Work

The accounting method provides a different, often more intuitive, lens. We use a financial analogy:

• We assign a specific amortized cost (a "payment" or "charge") to each type of operation. This is our analytical cost, not the actual cost.
• When an operation's amortized cost is higher than its actual cost, we "overpay" and store the difference as credit.
• When an operation's amortized cost is lower than its actual cost, we use the stored credit to pay for it.
• The Golden Rule: The total credit stored in the data structure must never become negative.

Let's see how this works with our two main examples: the multi-pop stack and the dynamic array.

Let's formalize the logic from the video:

Accounting for the Multi-pop Stack:

• Amortized Costs: PUSH = 2, POP = 0, MULTIPOP = 0.
• Actual Costs: PUSH = 1, POP = 1, MULTIPOP(k) = k.
• Analysis:
  • When we PUSH an element, we pay 2 coins. 1 coin pays the actual cost of the push. The other coin is stored with the element on the stack.
  • When we POP or MULTIPOP an element, its actual cost of 1 is paid for by the coin stored with it.
  • The total credit is the number of items on the stack, which is always $\ge 0$. The rule holds.
  • Since the highest amortized cost is 2, the amortized cost per operation is O(1).

Accounting for the Dynamic Array:

• Amortized Cost: append = 3.
• Actual Costs: append without resize = 1. append with resize = n + 1 (to copy n old items and add the new one).
• Analysis:
  • When we append an element, we pay 3 coins.
  • 1 coin pays the actual cost of insertion.
  • 2 coins are stored as credit.
  • Let's consider an array that just resized from size m to 2m. It currently holds m elements. The next m insertions will fill the array.
  • During these m insertions, we collect m * 2 = 2m coins of credit.
  • When the (2m+1)-th element is added, a resize is triggered. The array has 2m elements to copy. The cost is 2m.
  • The 2m coins of credit we saved are used to pay for this copy. The system is solvent.
  • The amortized cost is a constant 3, so the operation is O(1).

Conclusion

This lesson concludes our foundational module on complexity analysis. We've moved from simple loop counting to analyzing complex recursive algorithms, and now to understanding the performance of sequences of operations.

Key Takeaways:

• Amortized analysis provides a more practical measure of performance for data structures where some operations are occasionally expensive. It gives the worst-case average cost over a sequence.
• The Aggregate Method calculates the total cost of a sequence of n operations and divides by n to find the amortized cost. It's conceptually simple but requires analyzing the entire sequence at once.
• The Accounting Method uses a financial analogy of "pre-paying" for expensive operations. It assigns amortized costs to individual operation types and uses "credit" to balance payments, ensuring the system never goes into "debt".

Next Lesson Preview:
We are now ready to dive into the core data structures and algorithms that form the bedrock of coding interviews. In our next module, "Core Data Structures: Arrays, Strings & Hash Maps," we will begin by learning how to apply the two-pointer technique to solve problems on sorted arrays in O(n) time. This is a classic interview pattern that relies on the kind of efficiency thinking we've been developing.