Foundations
Amortized Analysis
Difficulty: Advanced
Appending to a Python list or JavaScript array almost always feels instantaneous, yet every so often the structure allocates a fresh buffer and copies every element into it, an O(n) operation. So why do textbooks still call append O(1)?...
Amortized Analysis
Appending to a Python list or JavaScript array almost always feels instantaneous, yet every so often the structure allocates a fresh buffer and copies every element into it, an O(n) operation. So why do textbooks still call append O(1)? Because amortized over a long sequence of appends, the rare expensive operation is paid for by many cheap ones. Amortized Analysis is the formal machinery that makes this kind of argument rigorous.
This lesson teaches the three classical methods. The aggregate method sums the total cost of n operations and divides by n for a per-operation bound. The accounting (banker's) method charges each operation a fixed amount and stores credits on the data structure to pay for future expensive ones. The potential (physicist's) method defines a potential function Phi and computes amortized cost as actual cost plus the change in Phi. You will apply all three to dynamic array doubling, stacks with multipop, and binary counters, and see how amortized O(1) differs from worst-case O(1) and from average-case analysis.
This lesson stands on the shoulders of Big-O Notation (Upper Bound) and Time Complexity Analysis Techniques. From those lessons you can already analyze a single operation; amortized analysis is what you reach for when the cost of one operation is misleading and the right object of study is a sequence of operations.
Next you will move to Recurrence Relations, the other major analysis tool, used when an algorithm's cost is most naturally written recursively rather than as a running total.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Distinguish amortized analysis from average-case and worst-case analysis with precise definitions.
Apply the aggregate method to compute amortized cost by dividing total cost over n operations.
Apply the accounting method by assigning credits to cheap operations and spending them on expensive ones.
Apply the potential method by defining a potential function and computing amortized cost as actual cost plus the change in potential.
Analyze dynamic array append operations to prove amortized O(1) cost using all three methods.
Identify real-world data structures and algorithms where amortized analysis applies.
Why This Matters
01
Many data structures (dynamic arrays, hash tables, splay trees, Union-Find) have operations that are occasionally expensive but cheap on average -- amortized analysis is the only correct way to prove this.
02
Without amortized analysis, you would overestimate the cost of n operations on a dynamic array as O(n^2) instead of the true O(n), leading to poor algorithm design decisions.
03
Interview questions about dynamic arrays, hash table resizing, and stack-based algorithms often require understanding amortized O(1) versus worst-case O(n) -- knowing the difference sets you apart.
04
Amortized analysis is a prerequisite for understanding advanced data structures like Fibonacci heaps, splay trees, and Union-Find with path compression.
Key Terms
8 terms you'll encounter in this lesson
Amortized Cost
The average cost per operation over a worst-case sequence of n operations. Unlike average-case analysis, it makes no probabilistic assumptions -- it guarantees that the total cost of any n operations is at most n times the amortized cost.
Aggregate Method
Compute the total worst-case cost T(n) for a sequence of n operations, then divide by n: amortized cost = T(n) / n. The simplest of the three methods.
Accounting Method (Banker's Method)
Assign an amortized cost (charge) to each operation. Cheap operations are overcharged to build up credits. Expensive operations spend those credits. The invariant: total credits must never go negative.
Potential Method (Physicist's Method)
Define a potential function Phi that maps each state of the data structure to a non-negative number. The amortized cost of an operation equals the actual cost plus the change in potential (Phi_after - Phi_before).
Credit (Accounting Method)
A prepaid unit of work stored with the data structure. Cheap operations deposit credits; expensive operations withdraw them. Credits are a bookkeeping device, not actual computation.
Potential Function
A function Phi: State -> R (real numbers) that measures how 'loaded' a data structure is. High potential means the structure has stored energy that will pay for future expensive operations. Phi must be >= 0 after any sequence of operations.
Dynamic Array (Resizable Array)
An array that doubles its capacity when full. Appending is O(1) most of the time but O(n) when resizing occurs. The amortized cost per append is O(1).
Multipop
A stack operation that pops up to k elements at once. A single multipop costs O(min(k, n)), but across a sequence of n push/multipop operations, the amortized cost per operation is O(1).
Heads Up
Common misconceptions to watch out for
"Amortized analysis is the same as average-case analysis"
Average-case analysis assumes a probability distribution over inputs and computes the expected cost. Amortized analysis makes no probabilistic assumptions -- it guarantees that the total cost of ANY sequence of n operations is bounded. It is a worst-case guarantee spread over multiple operations.
"An amortized O(1) operation means every single call is O(1)"
Individual operations can still be expensive (e.g., O(n) when a dynamic array resizes). Amortized O(1) means that over any sequence of n operations, the total cost is O(n), so the average per operation is O(1). Some calls are cheap, some are expensive, but they balance out.
"Credits in the accounting method represent real memory or computation"
Credits are purely an analysis tool -- a bookkeeping fiction. They do not affect the algorithm's runtime or memory usage. They exist only in the proof to show that expensive operations are 'paid for' by earlier cheap operations.
"The potential function must be unique for a given data structure"
There is no single correct potential function. Different potential functions can give valid (but possibly different) amortized bounds. The art is choosing a potential function that makes the analysis work out cleanly. A good potential function captures how 'far from ideal' the structure is.