1. Concept library
  2. Data Structures & Algorithms
  3. Module 1: Complexity analysis

Concept

Amortised cost

Some operations are expensive occasionally and cheap the rest of the time, like a dynamic array doubling when full. Amortised analysis averages the cost over a sequence, which is the number that matters in practice.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain why a dynamic array's append is amortised O(1)
  2. Work out the amortised cost of a sequence of operations
  3. Explain the difference between amortised and worst-case cost

In practice

A few lines that show Amortised cost doing its job.

Python
import sys

items = []
previous = sys.getsizeof(items)
for i in range(20):
    items.append(i)
    size = sys.getsizeof(items)
    if size != previous:
        print(f"grew at length {len(items)}")  # only a few times
        previous = size
# Each append is O(1) amortised, even though a few copy everything.

The common mistake

Watch for

Assuming amortised O(1) means every call is fast. A single resize can be slow, which matters in latency-sensitive loops; worst case and amortised case answer different questions.

What to know first

Your roadmap puts these before Amortised cost, unless you already know them.

How it stays learned

Once a session shows you understand Amortised cost, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Time versus space