Amortized Time Complexity: Definition and Examples

Amortized time complexity measures the average cost per operation over a sequence of operations on a data structure, even when some individual operations are expensive. Unlike worst-case analysis (which looks at a single operation in isolation) or average-case analysis (which relies on probability), amortized analysis guarantees that any sequence of n operations will take at most a certain total time, regardless of the order or pattern of operations.

Key Idea

Some operations are cheap most of the time but occasionally trigger an expensive "cleanup" or "resize" step. Amortized analysis spreads the cost of these rare expensive operations across the many cheap ones that precede them, showing that the average cost per operation remains low. Formally, if a sequence of m operations costs at most T(m) total time, the amortized cost per operation isT(m) / m.

Three Methods of Amortized Analysis

There are three standard techniques for performing amortized analysis:

1. Aggregate Method: Compute the total cost of m operations, then divide by m. 
2. Accounting (Banker's) Method: Assign a "charge" to each operation; cheap operations overpay and store credit to subsidize expensive ones. 
3. Potential Method: Define a potential function Φ that represents stored "energy"; amortized cost = actual cost + change in potential.

Classic Example 1: Dynamic Array (ArrayList, Python list, C++ vector)

The Problem 

A dynamic array starts with a small fixed capacity and grows as elements are appended. When the array is full, it must allocate a larger array and copy all existing elements—a costly O(n) operation. 

Naive Approach: Increase by 1 

If the array grows by just 1 slot each time it fills up:

• The i-th insertion costs O(i) to copy i−1 elements. 

• Total cost for n insertions: 1 + 2 + 3 + ... + n = O(n²). 

• Amortized cost: O(n²) / n = O(n) per insertion. 

This is inefficient. 

Smart Approach: Doubling Strategy 

Instead, double the capacity whenever the array is full: 

• Most insertions cost O(1) (just place the element). 

• Occasionally, when capacity is reached (at sizes 1, 2, 4, 8, ...), copy all elements to a new array of double size—costing O(n) for that insertion. 

Aggregate Analysis 

For n insertions:

• Cost of n simple insertions: n × O(1) = O(n). 

• Cost of all resizing operations: 1 + 2 + 4 + 8 + ... + 2ᵏ ≤ 2n (geometric series, where 2ᵏ ≤ n). 

• Total cost: O(n) + O(2n) = O(3n) = O(n). 

• Amortized cost per insertion: O(n) / n = O(1). 

Even though some insertions are O(n), the average is constant. 

Accounting Method Explanation 

Charge each insertion $3: 

• $1 pays for the actual insertion. 

• $2 is stored as credit on the newly inserted element. 

When resizing from size n to 2n: 

• The n/2 most recently added elements each have $2 credit, totaling $n.

• This credit pays for copying all n elements to the new array. 

• The current insertion still costs $1, so total charge remains $3. 

Thus, every insertion has an amortized cost of O(1). 

Potential Method 

Define potential Φ = 2 × (number of elements) − (capacity). 

• For a normal insertion: actual cost = 1, potential increases by 2 → amortized cost = 1 + 2 = 3. 

• For a resize: actual cost = n, potential drops by n → amortized cost = n − n = 0. 

Again, amortized cost per operation is O(1).

Classic Example 2: Hash Table with Resizing

Hash tables provide O(1) average-case lookup, insertion, and deletion. However, when the load factor (elements / buckets) exceeds a threshold, the table must resize and rehash all elements—an O(n) operation. 

Amortized Analysis 

Using the doubling strategy (like dynamic arrays): 

• Most insertions cost O(1) (hash and place in bucket). 

• Occasional resizing costs O(n) to rehash all elements. 

For n insertions:

• Total hashing operations: n (initial) + 1 + 2 + 4 + ... + 2ᵏ ≤ 3n. 

• Amortized cost per insertion: O(3n) / n =O(1).

This is why hash tables are said to have O(1) amortized time complexity for insertions, even though worst-case individual operations are O(n).

Classic Example 3: Queue Using Two Stacks

A queue (FIFO) can be implemented with two stacks (LIFO): 

• Enqueue: Push onto stack_in (O(1)). 
• Dequeue: If stack_out is empty, pop all elements from stack_in and push them onto stack_out (O(n)), then pop from stack_out (O(1)). 

Amortized Analysis 

•  Each element is pushed onto stack_in once, moved to stack_out once, and popped once. 
•  Total cost for n enqueue + n dequeue operations: O(3n) = O(n). 
•  Amortized cost per operation: O(n) / (2n) = O(1). 

Even though a single dequeue can be O(n), the average over many operations is constant.

Comparison Table

Data Structure	Operation	Worst-Case	Amortized	Why?
Dynamic Array	Append	O(n)	O(1)	Doubling spreads resize cost
Hash Table	Insert	O(n)	O(1)	Rehashing is rare with geometric growth
Two-Stack Queue	Dequeue	O(n)	O(1)	Each element moved at most twice
Disjoint Set (Union-Find)	Find/Union	O(log n)	O(α(n)) ≈ O(1)	Path compression + union by rank

Important Distinctions

Concept Definition Applies To Worst-case Maximum time for a single operation Any single operation Average-case Expected time over random inputs Probabilistic analysis Amortized Average time over any sequence of operations Sequence of operations on a data structure Crucial: Amortized analysis does not assume random inputs—it guarantees performance for the worst possible sequence of operations.

When Amortized Analysis Fails

Amortized O(1) relies on geometric growth (doubling). If a dynamic array grows by a fixed increment (e.g., +100 slots):

• Resizing occurs O(n) times for n insertions. 
• Each resize copies O(n) elements on average. 
• Total cost: O(n²) → Amortized cost: O(n), not O(1).

Takeaway

Amortized time complexity reveals that some data structures are far more efficient in practice than their worst-case per-operation analysis suggests. By analyzing sequences of operations rather than isolated steps, we can prove strong guarantees—like O(1) amortized time for dynamic arrays and hash tables—that make these structures indispensable in real-world software.