DailyRNG
Login
Advanced

Amortized cost

An operation that is sometimes cheap and occasionally expensive is measured by the average over a long run. That is the amortized cost.

What you will see

True

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Measure an amortized operation.

1

Doublings for 8.

n = 8 size = 1 doublings = 0 while size < n: size *= 2 doublings += 1 print(doublings)

Before you run it, say out loud what it will print. Then open the answer.

What it prints
3
2

Copies for 8.

n = 8 size = 1 copied = 0 while size < n: copied += size size *= 2 print(copied)

Before you run it, say out loud what it will print. Then open the answer.

What it prints
7
3

Two pointers of 4.

a = [1, 2, 3, 4] i, j, steps = 0, len(a) - 1, 0 while i < j: steps += 1 i += 1 j -= 1 print(steps)

Before you run it, say out loud what it will print. Then open the answer.

What it prints
2
4

Copies under 2n for 16.

n = 16 size = 1 copied = 0 while size < n: copied += size size *= 2 print(copied < 2 * n)

Before you run it, say out loud what it will print. Then open the answer.

What it prints
True

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Amortized cost is the total over a long run divided by the operations. Append doubles room, so it stays constant on average.
1 find the rare big step
↓
2 total the whole run
↓
3 divide by operations
↓
4 check the spikes
Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

n = 8 sets nothing on screen
size = 1 sets nothing on screen
doublings = 0 sets nothing on screen
while size < n: sets nothing on screen
size *= 2 sets nothing on screen
doublings += 1 sets nothing on screen
print(doublings) 3
Why this works
Average over a run

Amortized cost is the total cost of a long run divided by the number of operations. It is not the worst single step.

Rare big steps still matter

An amortized constant hides an occasional linear step. Real time can spike even when the average is flat.

Examples

Append grows

n = 8
size = 1
doublings = 0
while size < n:
    size *= 2
    doublings += 1
print(doublings)

A list doubles its room occasionally. For eight appends there are three doublings.

Copy cost is rare

n = 8
size = 1
copied = 0
while size < n:
    copied += size
    size *= 2
print(copied)

Each doubling copies the items so far. For eight appends that is 1 plus 2 plus 4.

Average per append

n = 8
size = 1
copied = 0
while size < n:
    copied += size
    size *= 2
print((copied + n) // n)

The copies total under 2n over n appends. Per append the average stays constant.

Two pointers

a = [1, 2, 3, 4]
i, j, steps = 0, len(a) - 1, 0
while i < j:
    steps += 1
    i += 1
    j -= 1
print(steps)

Two ends moving inward cost n over two turns. That is still linear.

A queue with two lists

inbox = [1, 2, 3]
outbox = []
outbox = inbox[::-1]
print(outbox.pop())

Reversing once when the outbox is empty spreads the cost over many pops. Each pop is constant on average.

Worst single step

n = 8
size = 1
worst = 1
while size < n:
    size *= 2
    worst = size // 2
print(worst)

One append can copy n items. The worst single step is linear even if the average is not.

Amortized is a run

n = 16
size = 1
copied = 0
while size < n:
    copied += size
    size *= 2
print(copied < 2 * n)

The total copies stay under 2n for the whole run. That is the amortized claim.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Cost of a recurrence
Previous Lesson
Cost of a recurrence
Next Lesson
Reading real costs
Reading real costs →