Amortized Analysis in Data Structures: Explained with Python
Spreading rare, expensive steps across many cheap operations—just like building savings over time—is the core principle behind amortized analysis in data structures.
Posted inDSA with Python

Amortized Analysis in Data Structures: Explained with Python

Posted by No Comments

This article Amortized Analysis is part of the Data Structures & Algorithms with Python roadmap. It builds directly on How to Analyze the Time and Space Complexity of an Algorithm, so read that one first if you haven’t.

Every Python tutorial says list.append() is O(1), yet every so often one append() copies the whole list. Both statements are true, and in this tutorial you will build a small dynamic array, measure it, and prove why.

Get the code

The complete, tested project for this tutorial is on GitHub. Clone it and follow along, or build each file as you read.

View the code on GitHub

What you’ll build and learn

You will build a small dynamic array that counts the work it does, then use it to show that its append() costs O(1) amortized even though one call can cost O(n). By the end, you’ll be able to:

  • Explain the difference between the worst-case cost of one call and the amortized cost over a sequence of calls
  • Implement a dynamic array that counts every item it copies
  • Prove the O(1) amortized bound with aggregate analysis, the accounting method, and the potential method, and check each proof with pytest
  • Compare your array with CPython’s real list using sys.getsizeof()
  • Show why growing by a fixed number of slots breaks the bound
  • Apply the same idea to a queue built from two stacks

Prerequisites: You should know basic Big O notation, be comfortable running Python files and pytest from a terminal, and have read type hints before. The code in this tutorial was run on Python 3.13.

What amortized cost means

Amortized cost is the worst-case total cost of any sequence of n operations, divided by n. Think of a $1,200 gym pass paid on January 1st. Nobody says the gym costs $1,200 on one day and $0 on the others. You say it costs about $100 a month, because you spread one big payment over the whole year.

When you read “amortized O(1)”, it means any sequence of n operations costs O(n) in total, so each operation is O(1) on average over that sequence, even if one of them is slow. Three points make the idea easy to hold on to:

  • It is a guarantee, not a guess. The bound holds for the worst possible sequence of operations, with no luck or probability involved.
  • It describes a sequence, not one call. A single call can still be slow.
  • Expensive steps must be rare. Each costly step has to be paid for by many cheap steps.

Amortized cost is not the same as average-case cost. Average-case analysis needs an assumption about the input: a dictionary lookup is O(1) on average only if hash values spread out well. Amortized analysis needs no assumption about the input, only a sequence of operations on the same data structure.

Step 1: Set up the project

The project is a flat folder of seven small files, so every import is a plain module name and every command runs from one place. Create the folder, a virtual environment, and install pytest:

$ mkdir amortized
$ cd amortized
$ python -m venv venv
$ source venv/bin/activate
(venv) $ python -m pip install pytest

On Windows, activate the environment with venv\Scripts\activate instead. You will create these files as you go:

amortized/
├── dynamic_array.py
├── analysis.py
├── two_stack_queue.py
├── measure.py
├── test_dynamic_array.py
├── test_analysis.py
└── test_two_stack_queue.py

The first three files hold the data structures and the cost helpers. measure.py prints the numbers you will study, and the three test_ files turn each claim in this tutorial into a check that either passes or fails.

git clone https://github.com/Emmimal/amortized-analysis-python.git
cd amortized-analysis-python
python -m venv venv
source venv/bin/activate
python -m pip install -r requirements.txt
python -m pytest

Step 2: Build an instrumented dynamic array

A dynamic array keeps free slots at the end. When they run out, it allocates a bigger block, copies every item across, and carries on. Think of a bookshelf: when it is full, you buy one twice as big and carry every book over. Save this as dynamic_array.py:

"""A dynamic array that counts how many items it copies."""

from collections.abc import Callable


def double(capacity: int) -> int:
    """Grow geometrically: the new capacity is twice the old one."""
    return capacity * 2


class DynamicArray:
    """A growable array backed by a fixed-size Python list.

    The array starts with room for one item. When it is full, it asks
    ``grow`` for a bigger capacity, allocates a new block, and copies every
    item across. Each copy is counted in ``copies``.
    """

    def __init__(self, grow: Callable[[int], int] = double) -> None:
        self._grow = grow
        self._capacity = 1
        self._size = 0
        self._slots: list[object] = [None] * self._capacity
        self.copies = 0

    @property
    def capacity(self) -> int:
        """Return how many items fit before the next resize."""
        return self._capacity

    def __len__(self) -> int:
        return self._size

    def __getitem__(self, index: int) -> object:
        if not 0 <= index < self._size:
            raise IndexError("index out of range")
        return self._slots[index]

    def append(self, value: object) -> None:
        """Add a value at the end, resizing first if the array is full."""
        if self._size == self._capacity:
            self._resize(self._grow(self._capacity))
        self._slots[self._size] = value
        self._size += 1

    def _resize(self, new_capacity: int) -> None:
        if new_capacity <= self._capacity:
            raise ValueError("new capacity must be larger than the old one")
        new_slots: list[object] = [None] * new_capacity
        for i in range(self._size):
            new_slots[i] = self._slots[i]
            self.copies += 1
        self._slots = new_slots
        self._capacity = new_capacity

The class uses a Python list only as a fixed-size block of slots. It never calls list.append() on it, so every resize is one you can see and count. Three details matter:

  • append() writes the value and finishes if there is room. That costs one step.
  • When the array is full, _resize() copies every item one by one, and copies goes up by one per item.
  • The growth rule is a parameter. It defaults to double(), and in Step 6 you will swap in a different rule to see what breaks.

Now turn those behaviors into checks. Save this as test_dynamic_array.py:

import pytest

from dynamic_array import DynamicArray


def test_items_keep_their_order() -> None:
    array = DynamicArray()
    for i in range(20):
        array.append(i)
    assert [array[i] for i in range(len(array))] == list(range(20))


def test_capacity_doubles_when_the_array_is_full() -> None:
    array = DynamicArray()
    capacities = []
    for i in range(9):
        array.append(i)
        capacities.append(array.capacity)
    assert capacities == [1, 2, 4, 4, 8, 8, 8, 8, 16]


def test_nine_appends_copy_fifteen_items() -> None:
    array = DynamicArray()
    for i in range(9):
        array.append(i)
    assert array.copies == 1 + 2 + 4 + 8


def test_index_out_of_range_raises() -> None:
    array = DynamicArray()
    array.append("a")
    with pytest.raises(IndexError):
        array[1]


def test_growth_function_must_increase_capacity() -> None:
    array = DynamicArray(grow=lambda capacity: capacity)
    array.append("a")
    with pytest.raises(ValueError):
        array.append("b")

Run the tests from the project folder:

(venv) $ python -m pytest test_dynamic_array.py

All five tests should pass. The third test already hints at the key fact of this tutorial: nine appends copy 1 + 2 + 4 + 8 = 15 items in total.

Step 3: Measure the cost of each append

One append costs more than one step only when it triggers a resize, so you need a precise cost to count. In this tutorial, the cost of an append is 1 for the write, plus 1 for every item copied. Start analysis.py with a helper that records that cost for each of n appends:

"""Helpers that turn a DynamicArray's work into numbers you can check."""

from collections.abc import Callable

from dynamic_array import DynamicArray, double


def append_costs(n: int, grow: Callable[[int], int] = double) -> list[int]:
    """Return the cost of each of n appends: one write plus items copied."""
    array = DynamicArray(grow)
    costs: list[int] = []
    for i in range(n):
        copies_before = array.copies
        array.append(i)
        costs.append(1 + array.copies - copies_before)
    return costs

The helper reads copies before and after each append, so the difference is exactly the number of items that call moved. Now create measure.py to print the numbers:

"""Measure the cost of appends and compare growth strategies."""

from analysis import append_costs
from dynamic_array import DynamicArray


def show_cost_per_append() -> None:
    print("Cost per append for a doubling array")
    for n in (10, 100, 1_000, 100_000):
        array = DynamicArray()
        for i in range(n):
            array.append(i)
        total_cost = n + array.copies
        print(f"n={n:>7,}  total cost={total_cost:>9,}  per append={total_cost / n:.2f}")


def show_first_costs() -> None:
    print("\nCost of each of the first 17 appends")
    print(append_costs(17))


if __name__ == "__main__":
    show_cost_per_append()
    show_first_costs()

Run it:

(venv) $ python measure.py
Cost per append for a doubling array
n=     10  total cost=       25  per append=2.50
n=    100  total cost=      227  per append=2.27
n=  1,000  total cost=    2,023  per append=2.02
n=100,000  total cost=  231,071  per append=2.31

Cost of each of the first 17 appends
[1, 2, 3, 1, 5, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1, 17]

Two patterns stand out. First, the input grew 10,000 times bigger, from 10 to 100,000 appends, yet the cost per append stayed between 2 and 3. That flat line is what amortized O(1) looks like in practice.

Second, the expensive appends are numbers 2, 3, 5, 9 and 17. They happen right after the size reaches 1, 2, 4, 8 and 16, so the gaps between them keep doubling. Costly steps get rarer as the array grows, and each one is paid for by a longer run of cheap appends.

Append-cost-chart-1024x512 Amortized Analysis in Data Structures: Explained with Python
Resizes are rare: only 6 of the first 33 appends cost more than 1, and the gaps between them keep doubling.
OperationWorst case (one call)Amortized
append()O(n)O(1)
Read by indexO(1)O(1)
Extra spaceO(n)O(n)

A single append is O(n) in the worst case because a resize copies n items. Over a long run, though, each append costs O(1) on average. The next step explains why that is always true.

Step 4: Prove the cost three ways

Measuring shows the pattern, and a proof shows it holds for every n. There are three standard methods, and you will turn each one into a pytest check.

Aggregate analysis: add everything up, then divide

Find the total cost of n appends in the worst case and divide by n. Every append writes one item, so the writes cost n in total. A resize happens when the size is 1, 2, 4, 8, and so on, and each resize copies that many items:

1 + 2 + 4 + 8 + ... + 2^k      where 2^k < n

This sum equals 2^(k+1) − 1, which is less than 2n. Check it with n = 9: the copies are 1 + 2 + 4 + 8 = 15, the writes are 9, the total is 24, and 3n is 27. Put the two parts together:

total cost = writes + copies < n + 2n = 3n
amortized cost per append = total cost / n < 3 = O(1)

The sum stays small because each resize is half the size of the next one. The last resize is as big as all the earlier ones put together, so the whole sum stays below twice the last term, and that is below 2n.

Save this as the start of test_analysis.py. It checks the first nine costs against the table from Step 3, then checks the 3n bound for every n up to 10,000:

from analysis import append_costs


def test_first_nine_costs_match_the_cost_table() -> None:
    assert append_costs(9) == [1, 2, 3, 1, 5, 1, 1, 1, 9]


def test_aggregate_total_cost_never_passes_three_n() -> None:
    total = 0
    for n, cost in enumerate(append_costs(10_000), start=1):
        total += cost
        assert total <= 3 * n

Accounting method: pay a little extra now

Imagine a jar labeled “moving day”. Every time you add an item, you drop a few extra coins into the jar, and a resize is paid for out of the jar. The method turns that into rules:

  1. Pick a fixed charge for each operation. This is the amortized cost you claim.
  2. If the real cost is less than the charge, save the difference as credit in the bank.
  3. If the real cost is more than the charge, pay the difference from the bank.
  4. The bank must never go below zero. If it does not, the charge is a valid amortized cost.

Charge 3 coins per append. One coin pays for writing the item now. One coin stays with the new item to pay for copying it at the next resize. The third coin stays with it to pay for copying one older item whose own coin is already spent. When the array of capacity C is full, half of its items are new since the last resize, each saved 2 coins, so the bank holds exactly C coins, and the resize copies C items.

Append #Real costChargeBank after
1132
2233
3333
4135
5533
6135
7137
8139
9933

The bank rises on cheap appends, drops on expensive ones, and never goes below zero. Add this helper to analysis.py:

def bank_balances(costs: list[int], charge: int) -> list[int]:
    """Return the bank balance after each operation (accounting method)."""
    balance = 0
    balances: list[int] = []
    for cost in costs:
        balance += charge - cost
        balances.append(balance)
    return balances

Then import it in test_analysis.py (from analysis import append_costs, bank_balances) and add two tests. The second one shows the charge cannot be a guess: two coins are not enough.

def test_accounting_charge_of_three_never_runs_out_of_credit() -> None:
    balances = bank_balances(append_costs(10_000), charge=3)
    assert min(balances) >= 0


def test_accounting_charge_of_two_runs_out_at_the_fifth_append() -> None:
    balances = bank_balances(append_costs(100), charge=2)
    first_negative = next(i for i, b in enumerate(balances, start=1) if b < 0)
    assert first_negative == 5

Potential method: energy stored in the structure

Think of a spring. Each cheap append winds it a little, and one resize releases it all at once. The potential method puts a number on that stored energy. You define a potential function Φ that looks at the state of the data structure, and the amortized cost of an operation is its actual cost plus the change in Φ:

$$\hat{c} = c + \Phi(\text{after}) - \Phi(\text{before})$$

For the dynamic array, this Φ works:

\Phi = 2 \cdot \text{size} - \text{capacity}

Right after a resize the array is about half full, so Φ is small. Each append raises Φ by 2, and when the array is full, Φ equals the number of items the next resize must copy. The stored energy matches the coming bill. Check both cases:

  • An append with room: the actual cost is 1 and Φ rises by 2, so the amortized cost is 1 + 2 = 3.
  • An append on a full array of c items: Φ before is 2c − c = c. The actual cost is c copies plus 1 write, so c + 1. After the resize the size is c + 1 and the capacity is 2c, so Φ after is 2(c + 1) − 2c = 2. The amortized cost is (c + 1) + (2 − c) = 3.

Both cases give 3. The big cost of copying c items is cancelled by the big drop in Φ.

Append #Actual costΦ beforeΦ afterAmortized cost
11−113
22123
33223
41243
55423
61243
71463
81683
99823

Φ starts at −1 because the empty array already owns one free slot. That offset does not matter, because Φ never ends lower than it started. Add these two functions to analysis.py:

def potential(size: int, capacity: int) -> int:
    """Return the potential function used for the dynamic array."""
    return 2 * size - capacity


def amortized_costs(n: int) -> list[int]:
    """Return actual cost + change in potential for each of n appends."""
    array = DynamicArray()
    result: list[int] = []
    for i in range(n):
        potential_before = potential(len(array), array.capacity)
        copies_before = array.copies
        array.append(i)
        actual = 1 + array.copies - copies_before
        potential_after = potential(len(array), array.capacity)
        result.append(actual + potential_after - potential_before)
    return result

Then import amortized_costs in test_analysis.py and add the last check:

def test_potential_method_gives_an_amortized_cost_of_three() -> None:
    assert set(amortized_costs(10_000)) == {3}

Run the whole suite:

(venv) $ python -m pytest

All ten tests should pass. The actual cost swings between 1 and 9, but the amortized cost is a calm 3 on every append.

Which method should you use?

All three prove the same result for the dynamic array. They differ in how they think about it.

MethodMain ideaBest when
AggregateTotal cost of n operations, divided by nThere is one kind of operation
AccountingCharge extra on cheap steps and keep the creditDifferent operations can have different charges
PotentialMeasure the energy stored in the structureThe structure is complex and you want a formal proof

Step 5: Compare with CPython’s real list

Python’s list is a dynamic array too, but it does not double. A list keeps its items in one continuous block of memory, and each slot holds a reference to an object, so copying a slot copies a reference, not the object. When append() finds no free slot, CPython asks for a bigger block, and it asks for extra room on purpose. That is called over-allocation.

You can see it with sys.getsizeof(). Add this function to measure.py, add import sys at the top of the file, and call show_cpython_growth() from the main block:

def show_cpython_growth() -> None:
    print("\nHow CPython's list grows")
    items: list[int] = []
    last_size = sys.getsizeof(items)
    print(f"len= 0 -> {last_size} bytes")
    for i in range(1, 65):
        items.append(i)
        size = sys.getsizeof(items)
        if size != last_size:
            print(f"len={i:>2} -> {size} bytes")
            last_size = size

On CPython 3.13 on a 64-bit machine, the output is:

How CPython's list grows
len= 0 -> 56 bytes
len= 1 -> 88 bytes
len= 5 -> 120 bytes
len= 9 -> 184 bytes
len=17 -> 248 bytes
len=25 -> 312 bytes
len=33 -> 376 bytes
len=41 -> 472 bytes
len=53 -> 568 bytes

The size does not change on every append. It jumps only at lengths 1, 5, 9, 17, 25, 33, 41 and 53, and between those jumps appends use free slots that were already reserved. Each slot takes 8 bytes, so each jump reserves room for 4, 8, 16, 24, 32, 40, 52 and 64 items.

The growth is about 12.5% plus a few extra slots, not an exact doubling. The exact numbers are an implementation detail and can differ between Python versions and between implementations such as PyPy. What matters is the shape: each new block is a constant factor bigger than the old one, which is the same property your doubling array has.

Why this tutorial counts instead of timing

You might try to time each append() and look for spikes. I tried this on one run of Python 3.13 with two million appends. A typical append took about 0.1 microseconds, and the appends that triggered a resize had a median of about 2.7 microseconds, so the resizes are visibly slower. But only 3 of the 50 slowest calls were resizes, because the operating system and the memory allocator add noise that has nothing to do with the algorithm. Your numbers will differ. Counting copies is deterministic, which is why the proofs in this tutorial count operations.

Step 6: See why growth must be geometric

What if the array grew by a fixed amount instead of a factor, say 10 slots each time? Your DynamicArray takes the growth rule as a parameter, so you can test that directly. Change the import in measure.py to from dynamic_array import DynamicArray, double, then add this rule and function, and call show_growth_strategies() from the main block:

def add_ten(capacity: int) -> int:
    """Grow by a fixed amount instead of by a factor."""
    return capacity + 10


def show_growth_strategies() -> None:
    print("\nItems copied: doubling vs adding 10 slots")
    for n in (1_000, 10_000, 100_000):
        doubling = DynamicArray(double)
        fixed = DynamicArray(add_ten)
        for i in range(n):
            doubling.append(i)
            fixed.append(i)
        print(f"n={n:>7,}  doubling={doubling.copies:>9,}  add 10={fixed.copies:>12,}")

The output shows the difference:

Items copied: doubling vs adding 10 slots
n=  1,000  doubling=    1,023  add 10=      49,600
n= 10,000  doubling=   16,383  add 10=   4,996,000
n=100,000  doubling=  131,071  add 10= 499,960,000

Look at the last row. Doubling copies about 131 thousand items, while adding 10 slots copies about 500 million. A fixed step means a resize every 10 appends, and each resize copies everything so far. The total grows like n² divided by 20, so the cost per append grows with n and is no longer amortized O(1).

Lock this in with one more test in test_analysis.py:

def test_fixed_growth_costs_far_more_per_append_than_doubling() -> None:
    n = 10_000
    doubling = sum(append_costs(n)) / n
    fixed = sum(append_costs(n, grow=lambda capacity: capacity + 10)) / n
    assert doubling < 3
    assert fixed > 100

Run python -m pytest again. All eleven tests should pass, and the last one confirms that the average cost per append with fixed growth is above 100 at n = 10,000, where doubling stays under 3.

The rule to remember: amortized O(1) appends need geometric growth. The array must grow by a factor, not by a fixed number of slots.

Step 7: Reuse the idea in a queue made of two stacks

Amortized analysis shows up wherever a costly step is rare and each item pays for it only once. A classic example is a first-in, first-out queue built from two stacks. Picture two trays of paper. New papers go on top of the inbox tray, so the oldest paper is stuck at the bottom. When you need it, you flip the whole inbox onto the outbox tray, which reverses the order. You then take papers from the outbox until it is empty, and only then flip the inbox again.

Save this as two_stack_queue.py. The moves counter works like copies in your array:

"""A first-in, first-out queue built from two stacks."""


class TwoStackQueue:
    """Queue that moves items between two lists only when it has to."""

    def __init__(self) -> None:
        self._inbox: list[object] = []
        self._outbox: list[object] = []
        self.moves = 0

    def __len__(self) -> int:
        return len(self._inbox) + len(self._outbox)

    def enqueue(self, item: object) -> None:
        """Add an item to the back of the queue."""
        self._inbox.append(item)

    def dequeue(self) -> object:
        """Remove and return the item at the front of the queue."""
        if not self._outbox:
            while self._inbox:
                self._outbox.append(self._inbox.pop())
                self.moves += 1
        if not self._outbox:
            raise IndexError("dequeue from empty queue")
        return self._outbox.pop()

One dequeue() can be slow. If the outbox is empty and the inbox holds n items, that single call moves all n of them, so the worst case for one call is O(n). Now count the work per item instead. Every item goes through exactly four steps in its life: pushed onto the inbox, popped off the inbox, pushed onto the outbox, and popped off the outbox. That is at most 4 basic steps per item, in any order of calls, so m operations cost at most about 4m steps in total. That is aggregate analysis again, and each enqueue() and dequeue() is O(1) amortized.

The accounting method agrees. Charge 3 coins for each enqueue(): one pays for the push now, and the other two stay with the item to pay for its later move between stacks. Charge 1 coin for each dequeue() to pay for the final pop.

Save these checks as test_two_stack_queue.py:

import pytest

from two_stack_queue import TwoStackQueue


def test_items_come_out_in_first_in_first_out_order() -> None:
    queue = TwoStackQueue()
    for i in range(1, 6):
        queue.enqueue(i)
    assert [queue.dequeue() for _ in range(3)] == [1, 2, 3]
    queue.enqueue(6)
    assert [queue.dequeue() for _ in range(3)] == [4, 5, 6]


def test_dequeue_from_an_empty_queue_raises() -> None:
    with pytest.raises(IndexError):
        TwoStackQueue().dequeue()


def test_each_item_moves_at_most_once() -> None:
    queue = TwoStackQueue()
    for i in range(1_000):
        queue.enqueue(i)
    for _ in range(500):
        queue.dequeue()
    for i in range(1_000, 1_500):
        queue.enqueue(i)
    while len(queue):
        queue.dequeue()
    assert queue.moves <= 1_500

Run python -m pytest one last time. All fourteen tests should pass, including the last one: 1,500 items were enqueued, and the queue moved each of them at most once.

This queue is a teaching tool. In real Python code, use collections.deque, which is built for this job.

When amortized O(1) is not enough

An amortized bound says nothing about one unlucky call, and that call pays the full price of the resize. Think of a commute that takes 20 minutes on a normal day and 2 hours longer once a month: the monthly average is a fine summary, but it does not help on the day you have a flight to catch. If total time matters, amortized analysis is the right tool. If the delay of a single call matters, look at the worst case.

SituationIs amortized O(1) enough?Why
A batch job that appends millions of itemsYesOnly the total running time matters
A web handler that appends a few itemsYesThe list is small, so a resize is cheap
A game loop with a fixed time budget per frameBe carefulOne slow call can make a frame late
Real-time audio or a control loop with hard deadlinesNoEvery single call must meet the deadline

If you know the final size in advance, you can skip the problem by reserving the space first:

# Reserve space once. No resize can happen while we fill it.
buffer: list[int | None] = [None] * 1_000_000
for i in range(1_000_000):
    buffer[i] = i

Common mistakes

  • Saying “append is always O(1)”. Say “O(1) amortized, and O(n) in the worst case for a single call”.
  • Mixing up amortized and average case. Ask whether the claim depends on lucky input. If it does, it is an average-case claim.
  • Treating every list operation as amortized O(1). list.insert(0, x) and list.pop(0) shift every remaining item on every call, so amortized analysis gives no discount. Use collections.deque for work at the front.
  • Forgetting that copies are never free. Slicing, list(items) and items + other copy the data, so each call is O(n).
  • Growing by a fixed amount. As Step 6 showed, the total copying becomes quadratic.

The front-of-the-list trap is easy to write by accident:

from collections import deque

line = deque([1, 2, 3])
line.popleft()  # O(1): removes from the front without shifting

items = [1, 2, 3]
items.pop(0)  # O(n): every remaining item shifts one place left

Both lines remove the first item, but in a loop over a large list the second one quietly turns an O(n) job into an O(n²) job.

Conclusion

You built a dynamic array that counts its own work and used it to show why list.append() is O(1) amortized even though one call can copy the whole list. Along the way, you:

  • Measured the cost per append and saw it stay between 2 and 3 while n grew 10,000 times
  • Proved the bound with aggregate analysis, the accounting method, and the potential method, and checked each proof with a pytest test
  • Compared your array with CPython’s list, which over-allocates by a constant factor instead of doubling
  • Showed that growing by a fixed number of slots makes the total copying quadratic
  • Reused the same idea for a queue made of two stacks

From now on, give both numbers when you describe an operation: “append() is O(1) amortized and O(n) in the worst case for a single call.” That one sentence shows you understand how the structure really works.

The same habit applies to code that looks slower than it is. When a while loop sits inside a for loop and the inner index never moves backward, ask how many times each item can be touched in total. If each item is pushed once and popped once, the whole loop is linear.

The full project, with all 14 tests and a README, is on GitHub at Emmimal/amortized-analysis-python.

Sources

What Cluster 1 gave you

This article closes the Foundations & Complexity cluster. Here is how the five articles fit together:

ArticleThe skill you gained
What Is Big O Notation?A language for how cost grows with input size
Best, Average, and Worst-Case Time ComplexityKnowing which case you are talking about
Recursion in PythonReading the call stack and the recursion tree
How to Analyze the Time and Space Complexity of an AlgorithmA repeatable process for any piece of code
Amortized Analysis (this article)Judging operations that are cheap most of the time

You now have the full toolkit for measuring code. Therefore, it is time to apply it to real data structures.

What to read next

The next cluster is Arrays & Strings. It starts with Arrays in Python: Operations, Complexity, and Common Patterns. You already know why append is cheap and why insert(0, x) is not. The next article builds on that and shows how arrays behave in everyday code.

If you want to see the whole path at once, the DSA with Python guide lays out every stage of the roadmap, from complexity to interview preparation.

Tags:
About the author Emmimal P Alexander is an AI Engineer and author dedicated to building applied AI systems that perform reliably in real-world production environments. She founded EmiTechLogic, an educational platform where she writes about neural networks, deep learning, large language models, and agentic AI—with a strong emphasis on practical engineering over idealized theory. Her background includes a BCA in computer applications, an MBA in business administration, and years of independent research and hands-on development in AI. She specializes in bridging theory to production-grade systems, tackling challenges like reliability, accountability, governance, AI hallucination, and well-defined decision boundaries. Emmimal is the author of Neural Networks and Deep Learning with Python: A Practical Approach and Agentic AI for Executives, where she explores not just models but the full systems around them—including failure modes and organizational risks. Through her writing, she prioritizes clarity over hype and sustainable impact over demos, helping practitioners and leaders understand how AI truly behaves when deployed. Check out her books on Amazon: https://www.amazon.com/stores/Emmimal-P-Alexander/author/B0DNGBTBRX
View All Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

  • Rating