🎓 A1Learner
🔍

DSA Amortised Analysis

Amortised analysis spreads the cost of rare expensive operations across many cheap ones. It prices a whole run of operations instead of judging each one alone.

Most appends cost one step

A doubling array copies its items when it outgrows its room. The copy cost lands on that one append.

def append_costs(n):
    size = 0
    capacity = 0
    costs = []
    for _ in range(n):
        cost = 1
        if size == capacity:
            cost += size
            capacity = max(1, capacity * 2)
        size += 1
        costs.append(cost)
    return costs

print(append_costs(10))

The total stays close to n

Sixteen appends include one copy of eight items. The total still lands under twice the append count.

def append_costs(n):
    size = 0
    capacity = 0
    costs = []
    for _ in range(n):
        cost = 1
        if size == capacity:
            cost += size
            capacity = max(1, capacity * 2)
        size += 1
        costs.append(cost)
    return costs

costs = append_costs(16)
print("appends:", len(costs), "total cost:", sum(costs))

One transfer per queue value

The two-stack queue moves each value from inbox to outbox once. Later dequeues never move it again.

inbox = [1, 2, 3, 4]
outbox = []
moves = 0
while inbox:
    outbox.append(inbox.pop())
    moves += 1
print("moves:", moves)
print("next out:", outbox[-1])

Example

def total_append_cost(n):
    size = 0
    capacity = 0
    total = 0
    for _ in range(n):
        total += 1
        if size == capacity:
            total += size
            capacity = max(1, capacity * 2)
        size += 1
    return total

for n in [10, 100, 1000]:
    total = total_append_cost(n)
    print("n =", n, "total =", total, "average =", round(total / n, 3))

class StackQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []
        self.transfers = 0

    def enqueue(self, value):
        self.inbox.append(value)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.transfers += 1
        return self.outbox.pop()

queue = StackQueue()
operations = 0
for value in range(200):
    queue.enqueue(value)
    operations += 1
for _ in range(200):
    queue.dequeue()
    operations += 1
print("queue operations:", operations)
print("queue transfers:", queue.transfers)

Key points

  • Amortised cost: the total cost of a run divided by the number of operations
  • A doubling array copies every item only when it outgrows its capacity
  • Expensive appends are rare because the capacity doubles each time
  • In the two-stack queue, each value moves across at most once
  • A whole run can stay cheap even when one step in it is expensive

In this example, the first table prices appends at three run lengths. The average cost falls toward two as the run grows, because the copies stay rare. The queue below settles the bill named in the Beginner course. Four hundred queue operations cause only two hundred transfers, one per value. The expensive first dequeue pays for itself across the whole run.

Note

Python lists reserve extra room as they grow, so list append is amortised constant time

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

One append in a doubling array copies 512 items in a single step. What does amortised analysis say about it?