Amortized Analysis

[!NOTE] This module explores the core principles of Amortized Analysis, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: Not All O(1) Are Created Equal

Inserting into a Dynamic Array (ArrayList) is O(1)… usually. Sometimes it triggers a resize, copying N elements (O(N)). So why do we say it is O(1)? Because the expensive operation happens so rarely that the average cost over time is constant. This is Amortized Analysis.

2. The Three Methods

A. Aggregate Analysis (Brute Force Average)

Show that a sequence of N operations takes T(N) time in total. Amortized Cost = T(N) / N.

  • Example: Resizing array. T(N) = N + N/2 + N/4 + … \approx 2N. Per op: 2N/N = O(1).

B. Banker’s Method (Accounting)

Charge extra for cheap operations (store “credits”). Use credits to pay for expensive operations.

  • Example: Charge $3 for every push.
  • $1 pays for the push itself.
  • $2 is saved in the bank.
  • When resize happens, we use the saved money to move the element.

C. Potential Method (Physics)

Define a potential energy function \Phi(D) for the data structure state. Amortized Cost = Real Cost + \Delta \Phi. If \Phi rises during cheap ops and drops during expensive ops, it smooths out the cost curve.

3. Case Study: Min-Stack

Problem: Implement a Stack with push, pop, and min() in O(1). Naive: Scan stack for min (O(N)). Amortized: Use a second stack to track min. Every push to main stack might push to minStack. Every operation is strictly O(1) (Real time, not just Amortized).

Wait, Dynamic Array Resize IS Amortized. A “Real-Time System” (like a heart monitor) cannot use Amortized O(1) because one single O(N) spike causes a stutter. They need Worst-Case O(1).

4. Deep Dive Strategy Lab: Amortized

Intuition Through Analogy

Rent vs. Buying.

  • Worst Case: Paying $500,000 for a house one day. (Expensive event).
  • Amortized: Living in it for 50 years. The cost per day is $27.
  • The “spike” of buying is smoothed out over the lifetime of usage.

Mathematical Anchor: Geometric Series

The cost of array resizing: 1 + 2 + 4 + 8 + … + N = 2N - 1 We double the size each time. The sum of powers of 2 converges to twice the last term. Total work is linear relative to the final size.