Amortized Analysis

Task: Watch what eight insertions really cost

Introduction

An operation can be expensive without making an algorithm expensive overall.

Imagine a dynamic array that is almost full.

Adding one more element may require creating a larger array and moving every existing element into it. That single insertion can take O(n) time.

But does that mean every insertion takes O(n)?

No.

Most insertions are cheap. The expensive resize happens only occasionally.

Amortized analysis gives us a way to measure the average cost of a sequence of operations, even when individual operations have very different costs.

Why Do We Need Amortized Analysis?

Consider adding elements to a dynamic array.

Most of the time:

Code

[10] [20] [30] [40]                         ↓ add 50[10] [20] [30] [40] [50]

The new element can simply be placed in the next available position.

That is:

O(1)

But eventually the array becomes full:

Code

[10] [20] [30] [40] [50]   ← full                         ↓                  create a larger array                         ↓[10] [20] [30] [40] [50] [60]

Now the existing elements have to be copied.

That operation costs:

O(n)

At first glance, it might seem that insertion into a dynamic array is O(n).

But that would give us the wrong picture.

The expensive resize does not happen on every insertion.

This is exactly the kind of situation amortized analysis helps us understand.

What Is Amortized Analysis?

Amortized analysis determines the average cost of operations over a sequence of operations, even when some individual operations are expensive.

The important word is sequence.

We are not asking:

"How expensive can this one operation be?"

We are asking:

"How expensive are these operations overall?"

This is different from average-case analysis.

Worst-case analysis

Looks at the most expensive possible individual operation.

Average-case analysis

Uses probabilities to estimate expected performance.

Amortized analysis

Looks at a sequence of operations and spreads the cost of expensive operations across the cheaper ones.

No probability is required.

The Dynamic Array Example

Suppose a dynamic array starts with capacity 1 and doubles whenever it becomes full.

We insert:

Code

12345678

The resize pattern looks like this:

Code

Insert 1 → no copyingInsert 2 → copy 1Insert 3 → copy 2 elementsInsert 4 → no copyingInsert 5 → copy 4 elementsInsert 6 → no copyingInsert 7 → no copyingInsert 8 → no copying

The individual costs are different:

Code

1, 2, 3, 1, 5, 1, 1, 1

Some operations are expensive.

But notice something important:

The expensive operations become less frequent as the array grows.

The array does not resize after every insertion.

So What Is the Amortized Cost?

Let's look at n insertions.

Most insertions cost approximately:

O(1)

The expensive resizing operations copy:

Code

1 + 2 + 4 + 8 + ...

elements.

Because the capacity doubles each time, this geometric series grows proportionally to n.

So across n insertions:

Code

Total work = O(n)

Therefore:

Code

Amortized cost per insertion= O(n) / n= O(1)

So although one insertion can cost O(n), insertion into a dynamic array has an amortized cost of O(1).

This does not mean every insertion takes O(1) time. A resize can still take O(n). It means that over a long sequence of insertions, the average cost per operation is O(1).

Amortized Does Not Mean Average Case

These two ideas are easy to confuse.

Suppose a dynamic array has this sequence:

Code

O(1)O(1)O(1)O(n)O(1)O(1)O(1)O(1)O(n)...

Amortized analysis asks:

How expensive is the entire sequence?

It does not ask how likely a resize is based on some probability distribution.

That is why amortized analysis can provide a guarantee even when we know nothing about how the operations are chosen.

Three Ways to Perform Amortized Analysis

There are three common techniques.

You do not need to master the mathematical details yet, but you should recognize the ideas.

1. Aggregate Method

Calculate the total cost of a sequence of operations and divide it by the number of operations.

For dynamic array insertion:

Code

Total cost of n insertions = O(n) Number of operations = n

Therefore:

Code

Amortized cost = O(n) / n               = O(1)

The aggregate method looks at the sequence as a whole.

2. Accounting Method

Imagine that cheap operations pay a little extra.

That extra "credit" is saved and later used to pay for an expensive operation.

For example:

Code

Normal insertion → actual cost = 1                   pay = 3 The extra 2 units become credit.

When resizing eventually happens, the saved credit helps pay for copying the existing elements.

The idea is simple:

Cheap operations build credit. Expensive operations spend it.

This is also called the banker's method.

3. Potential Method

The potential method assigns a stored value, called potential, to the current state of the data structure.

Think of it like energy stored inside the data structure.

A cheap operation may increase the potential.

Later, an expensive operation uses that stored potential to offset its cost.

The mathematical form is:

Code

Amortized cost= Actual cost  + Change in potential

You may encounter this method when studying more advanced algorithms and data structures.

For now, understanding the intuition is enough.

A Second Example: Stack Operations

Consider a stack with:

Code

push()pop()

Normally, each operation takes:

O(1)

Now imagine a slightly different operation:

Code

popAll()

It removes every element currently in the stack.

If there are n elements, one popAll() operation costs:

O(n)

But suppose each element can be removed only once.

Across a sequence of operations, an element cannot be removed repeatedly.

So if we perform many stack operations, the total number of removals is bounded by the number of elements that were pushed.

This allows us to reason about the total cost of the entire sequence, rather than treating every popAll() as independently expensive.

That is the core mindset behind amortized analysis.

Amortized vs Worst Case

This distinction is particularly important in interviews.

Consider dynamic array insertion:

Analysis	Cost
Best case	O(1)
Worst-case individual insertion	O(n)
Amortized insertion	O(1)

All three are correct. They answer different questions.

These statements are all correct.

They answer different questions.

Worst case: What is the most expensive single insertion?

Amortized: What is the average cost per insertion across a sequence?

Do not replace one with the other.

Where You Will See Amortized Analysis

You will encounter amortized analysis primarily when a data structure occasionally performs an expensive operation to make future operations cheaper.

Common examples include:

Dynamic arrays
Hash tables during resizing
Disjoint-set union with optimizations
Certain stack and queue implementations
Some advanced tree and data-structure operations

The pattern is usually:

Code

Many cheap operations        ↓Occasional expensive operation        ↓Overall cost remains efficient

Once you recognize this pattern, amortized analysis becomes much easier to understand.

A Useful Mental Model

Think of amortized analysis like paying for a large purchase with small contributions.

Imagine every operation costs one coin.

Most operations pay exactly one coin.

Occasionally, an operation needs ten coins.

Instead of saying:

"That operation costs ten coins, so everything is expensive."

we look at the entire sequence.

If earlier operations accumulated enough extra credit to pay for it, the overall cost can still be small.

Code

Cheap → Cheap → Cheap → Expensive  ↓       ↓       ↓         ↓ +2      +2      +2      spend 6

The expensive operation is real.

We simply account for its cost across the sequence.

Common Mistakes

Watch out

Saying amortized O(1) means every operation is O(1).

It does not. An individual operation can still take O(n).

Confusing amortized analysis with average-case analysis.

Amortized analysis does not require probabilities.

Ignoring expensive operations.

They are still part of the total cost. Amortized analysis simply distributes that cost across the sequence.

Using amortized complexity as the worst-case complexity of one operation.

For dynamic arrays, insertion can still have a worst-case cost of O(n) even though its amortized cost is O(1).

Quick Check

1. A dynamic array insertion occasionally takes O(n) because the array must resize. What is the amortized cost of insertion when the capacity doubles each time?

2. A dynamic array is inserted into 8 times, starting from capacity 1. What does each insertion cost, and what is the total?

3. What is the difference between amortized analysis and average-case analysis?

4. If a data structure grew its capacity by a fixed 1 slot instead of doubling, what would the amortized cost of insertion become?

5. Is it correct to say that insertion into a dynamic array is O(1) in the worst case?

Show answer

O(1). Although an individual resize can take O(n), resizing happens infrequently enough that the total cost of n insertions is O(n). Therefore the amortized cost per insertion is O(1).
1, 2, 3, 1, 5, 1, 1, 1, which is 15 units in total. The three resizes land at insertions 2, 3 and 5, copying 1, 2 and 4 elements.
Average-case analysis uses probabilities to estimate expected performance. Amortized analysis looks at the total cost of a sequence and requires no probability at all.
O(n). Every insertion would copy everything, so n insertions would cost about n²/2 in total. The doubling is what makes the copying rare enough to amortize away.
No. The worst case for a single insertion is O(n), because that insertion may be the one that resizes. O(1) is its amortized cost, which answers a different question.

Quick Recap

Amortized analysis studies the cost of a sequence of operations.
An individual operation can be expensive while the overall sequence remains efficient.
It does not require probability.
Dynamic array insertion is the classic example.
A dynamic array insertion can take O(n) in the worst case.
Its amortized cost is O(1) when capacity grows geometrically.
The three standard techniques are the aggregate method, the accounting method and the potential method.
Amortized complexity should not be confused with worst-case complexity.

Where This Leads

You have now completed the Complexity foundation:

Code

Time Complexity      ↓How much work does the algorithm do? Space Complexity      ↓How much additional memory does it need? Amortized Analysis      ↓How does the cost behave across many operations?

These three ideas form the foundation for analyzing the efficiency of the data structures and algorithms you are about to learn.

Amortized analysis does not make expensive operations disappear. It shows how their cost is distributed across an entire sequence of operations.